Sorting a linked-list with ascending/descending option

Question

I need to implement sortList which should sort a linked list by name, and the second argument determines whether it should sort ascending or descending.

The functions newItem and freeList are mandatory, but I have implemented them without issues.

My problem is with the function sortList, which depends on compare, and changeListPointers: I couldn't make it work as expected.

This is the code I've tried:

typedef struct TItem {
    struct TItem *m_Next;
    char *m_Name;
    char m_Secret[24];
} TITEM;

//mandatory function
TITEM *newItem(const char *name, TITEM *next) {
    TITEM *result = (TITEM *) malloc((sizeof(TITEM)) + 4);  //creates new Item, if the sizeof is 0 then it adds 4B
    result->m_Next = next;
    result->m_Name = strdup(name);
    return result;
}

int compare(TITEM * firstName, TITEM * secondName) {
    if(firstName->m_Name != NULL || secondName->m_Next->m_Name != NULL){
    return strcmp(firstName->m_Name, secondName->m_Next->m_Name);
    }else {
        // if the last list is null what next?
    }
}

int changeListPointers(TITEM * firstBox, TITEM * secondBox) {   //
    if(firstBox->m_Name != NULL || secondBox->m_Next->m_Name != NULL){
        firstBox->m_Name, secondBox->m_Next->m_Name;
        return 1;
    }else{
        return 0;
    }

}

//mandatory function
TITEM *sortList(TITEM *l, int ascending) {  // should sort the lists by m_Name
    int compareWords = compare(l, l);

    if(ascending == 0){ //sort in descending order
        if(compareWords >= 1){
            //  redo pointers
            changeListPointers(l,l);
        }else{
            //first one is bigger second one is smaller do nothing
        }
    }else{

    }
}

//mandatory function
void freeList(TITEM *src) {     //frees up allocated memory
//loops through the link list until it finds the last one which will have NULL value
    while (src != NULL) {       
        TITEM *next = src->m_Next;  
        free(src);                  //frees the list value
        src = next;
    }
}

int main(int argc, char *argv[]) {
    TITEM *l;
    char tmp[50];

I would be grateful if there is an easy solution to fix my code.

Answer 1

From your compare function it seems like you always want to compare two adjacent names. I would suggest sorting with merge sort, where you will compare nodes that are not necessarily adjacent.

Here are some functions you could use for implementing merge sort:

int listSize(TITEM *l) {
    int count = 0;
    while (l != NULL) {
        count++;
        l = l->m_Next;
    }
    return count;
}

// Split list in two halves, the pointer to the second halve is returned
TITEM *splitList(TITEM *l) {  
    int halfCount = listSize(l) / 2;
    if (halfCount == 0) return NULL;
    TITEM *curr = l;
    while (--halfCount) {
        curr = curr->m_Next;
    }
    TITEM *l2 = curr->m_Next;
    curr->m_Next = NULL;
    return l2;
}

// Compare two nodes by their name, negating the result when descending is indicated
int compare(TITEM *l1, TITEM * l2, int ascending) {
    int cmp = strcmp(l1->m_Name, l2->m_Name);
    return ascending ? cmp : -cmp;
}

// Merge two sorted lists into one sorted list
TITEM *mergeLists(TITEM *l1, TITEM *l2, int ascending) {
    TITEM *dummy = newItem("", NULL);
    TITEM *tail = dummy;
    while (l1 != NULL && l2 != NULL) {
        if (compare(l1, l2, ascending) > 0) {
            tail->m_Next = l2;
            l2 = l2->m_Next;
        } else {
            tail->m_Next = l1;
            l1 = l1->m_Next;
        }
        tail = tail->m_Next;
    }
    tail->m_Next = l1 == NULL ? l2 : l1;
    return dummy->m_Next;
}

//mandatory function
TITEM *sortList(TITEM *l, int ascending) {  // should sort the lists by m_Name
    TITEM *l2 = splitList(l);
    if (l2 == NULL) return l; // base case
    return mergeLists(sortList(l, ascending), sortList(l2, ascending), ascending);
}