I am trying to use insertion sort on a singly linked list, where each node has multiple parameters, say:
typedef struct _node {
char param1[10];
char param2[10];
char param3[10];
struct _node *next;
} node;
The algorithm would sort the list by param1, and in case of equivalent items decide the order by param2, and similarly by param3. I was unable to find a solution to this problem online. For a single parameter, I've got the following implementation of the sorting algorithm to work:
void insertionSort(node **head) {
//Initialize sorted list
node *sorted = NULL;
node *current = *head;
//Insert every node into sorted list
while (current != NULL) {
// Store next for next iteration
node *next = current->next;
sortedInsert(&sorted, current);
// Update current
current = next;
}
//Replace old empty list with sorted list
*head = sorted;
}
void sortedInsert(node **head, node *new) {
node *current = *head;
// Special case for the head
if (current == NULL || strcmp(current->param1, new->param1) >= 0) {
new->next = current;
*head = new;
}
else {
while (current->next!=NULL && strcmp(current->next->param1, new->param1) < 0){
current = current->next;
}
new->next = current->next;
current->next = new;
}
}
My guess would be that I have to create a comparison function instead of the following bits, maybe an integer function returning 0 or 1 corresponding to the two cases:
current->param1 >= new->param1
current->next->param1 < new->param1
However, I am unable to come up with such a function. Could anyone help me out with this?
