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;
        }
    }
}

What exact part of the insertion sort algorithm do you think is incompatible with single linked lists? — n. m. could be an AI
– n. m. could be an AI, Commented May 23, 2017 at 16:05
This article might be useful for what you're trying to achieve. geeksforgeeks.org/insertion-sort-for-singly-linked-list — Vic
– Vic, Commented May 23, 2017 at 16:16
You can't "travel" back in a singly linked list and isn't that exactly what you need to do for insertion sort? — Dennis
– Dennis, Commented May 23, 2017 at 16:17
Indeed, that's why you need to have a second singly linked list in order to apply the insertion sort technique. You should read the article that I just gave it to you. — Vic
– Vic, Commented May 23, 2017 at 16:23
You basically need a pointer to the thing that was pointing to the element you are moving (possibly a pointer to a link pointer if you want to avoid a special case for the element at the beginning of the list), and a pointer to the element before the new position of the element you are moving (again, possibly a pointer to a link pointer). — Ian Abbott
– Ian Abbott, Commented May 23, 2017 at 16:32

John Bollinger · Accepted Answer · 2017-05-23 19:02:01Z

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.

Collectives™ on Stack Overflow

C Programming - Insertion Sort in Singly Linked List

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related