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?

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

All 4 Replies

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))

@geojia ...
Is insertion sort O(nlogn) or O(n^2) sort.Read yourself first

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.

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.