C Programming - Insertion Sort in Singly Linked List

Question

I'm almost done with my assignment, the last part is to write a function that sorts a singly linked list via insertion sort.. I'm also bound by my assignment's pre-defined structs and typedefs:

struct le {
    int value;
    struct le *next;
};

typedef struct le listenelement;
typedef listenelement *list;

Those I can't change. The insertion sort function has to work with these parameters. If the parameter m is negative, the list is supposed to be sorted in descending order and otherwise in ascending order.

void sort(int m, list *l);

EDIT:

Here's my attempt to implement the answers from here.. I still can't get it to work. I tried creating a new list that is the final result called "asc" (for ascendingly sorted list) and an auxiliarly list "aux" but I'm stuck..

void sort(int m, list *l){              
    if ((m == 0) || (*l == NULL)) {
        printf("Error.\n");
    } else {
        if (m>0) {
            listenelement head = {0,NULL};              
            list asc = {&head};
            list aux = *l;
            while (aux != NULL) {                       
                int val = aux->value;                                                   
                delete_elem(val,&aux);                                                  
                while ((asc->next != NULL) && ((asc->value)<val)) {         
                    printf("%d\n", (asc->value));                                       
                    asc=asc->next;
                }
                insert(val,&asc);   
                asc = &head;                            
            }
            *l = &head;
        }
    }
}

Answer 1

insertion sort can't work on a singly linked list, can it? You can only go forward in them.

The usual insertion sort implementation for arrays has no exact analog that works well with singly-linked lists, but that doesn't mean that the algorithm cannot be applied to such lists. You just need a broader understanding of the algorithm, which Wikipedia characterizes as:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Observe that that characterization has no dependency on the order in which you can traverse the items. You're stuck on the usual implementation of the insertion step, which involves iterating backward through the list to find the insertion position. You actually could do that with your singly-linked list, in the sense of testing each previous element from nearest to most distant, but that would change the overall algorithm's asymptotic complexity to O(N³). Not good. And not necessary.

What's wrong with finding the insertion position by iterating forward through the sublist from the beginning? That still satisfies the algorithmic definition (as given by Wikipedia), preserves the asymptotic complexity, and in the general case it gets just as much advantage from the initial sublist being in sorted order as does the usual implementation.

The main thing that differs is the best- and wort-case scenarios. The best case for the usual implementation is that the elements are initially in order, and the worst case is that they are initially in reverse order. Those are simply flipped for a naive implementation of the iterate-forward approach, but with a linked list and careful implementation those two cases can be made almost equally good. The iterate-backward implementation does have some additional practical implications for arrays, but those do not apply to linked lists.