CODEWITHSUNDEEP
c
J Szum
J Szum

Reputation: 515

Sorting Linked List with Two Parameters in C

The linked list contain two types of data - int count and float rank. The list needs to be sorted in descending order based firstly on count and then on rank. I have sorted the list based on count, but it appears I don't get the process completely.

I understand that if current count is equal to the next count, then compare rank and insert node with higher rank.

I have changed the code after the comment, however it does output data correctly (does not sort by the rank). How can I fix it?

Sorted list by the first parameter (what I currently get):

2, 0.152009
2, 0.077676
2, 0.092575
2, 0.157685
1, 0.262355
1, 0.184311
1, 0.073388

Expected output after sorting list by the second parameter:

2, 0.157685
2, 0.152009
2, 0.092575
2, 0.077676
1, 0.262355
1, 0.184311
1, 0.073388

My code:

typedef struct node {
    int count;
    float rank;
    struct node *next;
} NodeT; 

void insertionSort(NodeT **head) {
    
    NodeT *sorted = NULL;
    NodeT *current = *head;
    while (current != NULL) {
        NodeT *next = current->next;
        sortedInsert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

void sortedInsert(NodeT **head, NodeT *new) {

    NodeT *current;

    if (*head == NULL || (*head)->count <= new->count) {
        new->next = *head;
        *head = new;

    } else {
        current = *head;
        while (current->next != NULL) {

            /* Should second parameter check go here? */

            if (current->next->count > new->count) {
                current = current->next;

            } else if (current->next->count == new->count) {

                while (current->next != NULL && current->next->rank > new->rank) {
                    current = current->next;
                } 
            }

        }
        new->next = current->next;
        current->next = new;
    }
}

Upvotes: 1

Views: 779

Answers (2)

Cheatah
Cheatah

Reputation: 1835

The "correct" way is probably to write a comparison function to avoid the two nested while loops.

int compare_nodes(NodeT *n1, NodeT *n2)
{
    if (n1->count < n2->count)
        return -1;
    if (n1->count > n2->count)
        return 1;
    if (n1->rank < n2->rank)
        return -1;
    if (n1->rank > n2->rank)
        return 1;
    return 0;
}

Now you should have a much easier time implementing the insert function.

Upvotes: 4

ralf htp
ralf htp

Reputation: 9422

In Is there a way to sort structs by multiple variables in C? is an example that uses qsort with a defined compare function (cmp()). It implements the nodes as struct, in main() the list is created...

An example for insertion sort is in Insertion sort array of structure by 2 fields

Upvotes: 1

Related Questions