Hello,

for a school assignment I was supposed to write an insertion sort algorithm for a doubly linked list. As the feedback system of this particular course is rather weak (actually non-existent) I would like to ask you for your honest opinion about how well this is implemented, what could be improved, made more efficient, etc?

Thanks in advance,

Marcel

    #include <iostream>
    using namespace std;

    class elem{

    public:
        int value;
        elem* prev;
        elem* next;

        elem(int e, elem* ptr1, elem* ptr2){
            value = e;
            prev = ptr1;
            next = ptr2;
        };

    };

    class list{

    private:
        elem* first;
        elem* last;
        int length;

        elem* last_sorted;
        elem* selected;

    public:
        list(){
            first = NULL;
            last =  NULL;
            length = 0;
        };

        void push(int a){
            if(length<1){
                length++;
                elem* new_elem = new elem(a, NULL, NULL);
                first = new_elem;
                last = new_elem;

            }else if(length>0){
                length++;
                elem* new_elem = new elem(a, NULL, NULL);
                last->next = new_elem;
                new_elem->prev = last;
                last = new_elem;
            }
        };

        int pop(){
            if(length>0){
                length--;
                int data = first->value;
                elem* temp = new elem(0, NULL, NULL);
                temp = first;
                first = first->next;
                delete temp;
                return data;
            }else{
                cout << "Empty!\n";
            }
        };


        void sort(){    
            //set the last sorted pointer to the first element in the list
            last_sorted = first;        

            //as long as the last sorted element is not the last element in
            //the list, perform the sorting:
            while (last_sorted != last){

                // for every new iteration, set the selected element to the 
                //element after last sorted

                selected = last_sorted->next;       
                // as long as selected is not the first element and its value 
                //is smaller than the previous change the position of 
                //selected and selected->prev

                while (selected->prev != NULL && selected->prev->value > selected->value){

                    //special case swarp1: selected->prev is the first 
                    //element
                    if(selected->prev == first){
                        selected->next->prev = first;
                        selected->prev = NULL;
                        first->next = selected->next;
                        first->prev = selected;
                        selected->next = first;
                        first = selected;

                    }
                    //special case swap2: selected is the last element
                    else if(selected == last){
                        last_sorted->next = NULL;
                        selected->next = last_sorted;
                        selected->prev = last_sorted->prev;
                        selected->prev->next = selected;
                        last_sorted->prev = selected;
                        last = last_sorted;
                    }
                    //regular case swap 
                    else{
                        selected->next->prev = selected->prev;
                        selected->prev->next = selected->next;
                        selected->prev->prev->next = selected;
                        selected->prev = selected->next->prev->prev;
                        selected->next = selected->next->prev;
                        selected->next->prev = selected;

                    }           
                }
                //check whether last sorted is smaller/equal to the next element: if yes, go on step further
                if(last_sorted->next != NULL && last_sorted->value <= last_sorted->next->value){
                last_sorted = last_sorted->next;
                }
            }
            cout << "sorted\n";
        }   
    };

    int main(){
        const int am =39;

            list a;

            for(int i=0;i<am;i++){
                int ran = rand()%100;
                a.push(ran);
                cout << ran << " is pushed\n";
                }

            a.sort();

            for(int i=0;i<am;i++){
                cout <<a.pop()<<endl;
                }

            return 0;
    }

Edited 4 Years Ago by marcelmarcelmarcelmarcelmarcelmarcelmarcelmarcel: formatting of code

Couple of things to note:
1. In your list constructor you need to link your head and tail, or the attributes are completely meaningless
2. When you add an element you need to link the head/tail node to the new node. Also code that appear in both the if and else should be taken out of the conditions since you are always going to do those operations
3. Whatever sort you do on a double linked list is going to be slow (O(n^2)). So insertion sort isn't what you are doing (insertion sort referrs to the O(nlogn) sorting algorithm) Not looking at your code too closely but I think you are actually doing a selection sort (O(n^2))

First, in real life one does not use linked lists, double or single, for sorting. You can achieve that by using a tree container. The exercise id good for teaching you how much overhead is in the misuse of this container!

This code does not sort on insert, it sorts and it inserts separately. Sorted insert says first you find the right place in the list, then insert the new item. This way, the list is sorted for any intermediate user to use. Real life apps have inquiry and deletion and updates as well as insertion, so delayed sorting means the list is invalid in the interim. Of course, for multithreaded or interrupted code, there needs to be locks that keep the other thread out until the list is intact again, especially a double linked list. A single linked list can insert by pointing the new element to the next, then the prior to the new, so before that last action, the list is short with a side twig, and after the last action it is longer, no intermediate state where the list is invalid. With double links, you can update the new for new neighbors, but then you must lock the list or neighbors while you update the lower one's next and the higher one's prior.

Sometimes speed is better if you take in items in a single linked list, or even except linked lists to add to an internal list of linked lists, so the caller is not held up. For instance, in multicore processing, each core can build a linked list and when it hits some size or event, pass that to the container to sort. Because it only inserts to the target container occasionally in bulk, and then it is just linked into a list, there is little lock waiting (high parallelism. Another thread or the reader incurs the overhead of sorting and merging these single linked lists into the sorted list, perhaps an internal, final tree container. Parallel thereads could take each submitted linked list and put it into a temporary internal tree, then pass that to a critical path tee update thread that merges trees into the main tree (merge of sorted sets is faster than random inserts). If your machine has 4096 Cores, this is a real winner. That is the future. The critical thread could even assign pairs of intermediate input trees to a parallel thread to merge, so it only has to deal with one input tree to merge. If the trees merged are equal in size, the merge is most efficient. The intermediate and final trees could be sorted by size and merged small to large.

BTW, sorting linked lists is most efficient if you consider the input linked list of N as a list of N sorted lists (of 1). A small array of pointers and a counter can support merging (zero-based numbering) 0 to 1, 2 to 3, 0-1 to 2-3, 4 to 5, 6 to 7, 4-5 to 6-7, 0-3 to 4-7, etc. The count read bits say when to merge, eg., after # 1, 3-twice, 5, 7-three times, based on low order ones (at 7 merge three times for 0111 base two), or if an after/one-based count low order zeroes (at 8 merge three times and have one list = 1000 base 2). This exploits locality of reference perfectly, for as lists get longer, you are sorting first in l3 cache, then a little in l2 cache, then a little in l1 cache, then a little in RAM, then a little on disk. All the merges of smaller lists remain in l3 cache.

The A is out thataway!

Do you understand how an 'insert-sorted' container is supposed to work, as you add/insert each next element?

Have you tested your code out with some random type data input to see if the output is correct at each step?

You might like to see some of these student type examples, to get some more ideas?

http://developers-heaven.net/forum/index.php/topic,310.0.html

http://developers-heaven.net/forum/index.php/topic,2606.0.html

http://developers-heaven.net/forum/index.php/topic,2613.0.html

Edited 1 Year Ago by David W

This article has been dead for over six months. Start a new discussion instead.