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