I have a program that sorts a linked list by string (m_Name values). The problem is that the program is unstable (I mean this: https://www.geeksforgeeks.org/stable-and-unstable-sorting-algorithms/ ).

Is there any way to fix my code to make the sort stable or should I create some other algorithm. Alternatively, do you know what kind of algorithm would be appropriate if I can't use any library for qsort etc.

All program https://onecompiler.com/c/3ysjeqn5j

Or if there is any material I can study to create a stable sort algorithm for linked list, please tell me.

TITEM *sortInsert(TITEM *newNode, TITEM *sorted) {
    //if (sorted || strcmp(sorted->m_Name, newNode->m_Name) == 0)
    //    return sorted;

    if (!sorted || strcmp(sorted->m_Name, newNode->m_Name) >= 0) {
        newNode->m_Next = sorted;
        sorted = newNode;
    } else { //Locate the node before the point of insertion
        TITEM *tmp = sorted;
   
        while (tmp->m_Next && strcmp(tmp->m_Next->m_Name, newNode->m_Name) < 0) {
            tmp = tmp->m_Next;
        }
      
        newNode->m_Next = tmp->m_Next;
        tmp->m_Next = newNode;
    }
    return sorted;
}

TITEM *sortList(TITEM *l, int ascending) {
    TITEM *tmp = l;
    TITEM *sorted = NULL;

    while (tmp) {
        TITEM *next = tmp->m_Next;
        sorted = sortInsert(tmp, sorted);
        tmp = next;
    }
    l = sorted;

    if (!ascending) {
        l = reverse(l);
    }

    return l;
}

CodePudding user response：

There are 2 problems in your approach:

• you are inserting the elements from the list one at a time into the sorted list, hence if the element is identical to some already in the sorted list, it should be inserted after the duplicates in order to stay in the same relative order. You must change the comparison operators to > and <= respectively.

• you cannot handle descending order by reversing the list as the duplicate elements are going to appear in reverse order too. A simple solution is passing the sort direction and multiplying the return value of strcmp() by either 1 or -1 depending on the direction. The duplicates will be kept in the original relative order as strcmp returns 0 for them in both directions.

Here is a modified version:

// insert a node according to sorting direction
TITEM *sortInsert(TITEM *newNode, TITEM *sorted, int dir) {
    if (!sorted || strcmp(sorted->m_Name, newNode->m_Name) * dir > 0) {
        newNode->m_Next = sorted;
        sorted = newNode;
    } else { //Locate the node before the point of insertion
        TITEM *tmp = sorted;
   
        while (tmp->m_Next && strcmp(tmp->m_Next->m_Name, newNode->m_Name) * dir <= 0) {
            tmp = tmp->m_Next;
        }
        newNode->m_Next = tmp->m_Next;
        tmp->m_Next = newNode;
    }
    return sorted;
}

TITEM *sortList(TITEM *l, int ascending) {
    int dir = ascending ? 1 : -1;
    TITEM *tmp = l;
    TITEM *sorted = NULL;

    while (tmp) {
        TITEM *next = tmp->m_Next;
        sorted = sortInsert(tmp, sorted, dir);
        tmp = next;
    }
    return sorted;
}