Bubble Sort on Linked List

[wpdm_package id=’1161′]

We have seen sorting on numbers in arrays. Now what about sorting a linked list using bubble sort? Before we continue, we must keep in mind that a list is more complex than an array. So while doing swapping, we must keep good care to keep track of the changes that would happen in the next pointers of each node.

Algorithm:

[sourcecode lang=”cpp”]

void bubble_sort ()
{
int count = 0, i;
intnode *start = head;
intnode *curr = NULL;
intnode *trail = NULL;
intnode *temp = NULL;

while(start != NULL) { //grab count
count++;
start = start->next;
}

for(i = 0; i<count; ++i) { //for every element in the list

curr = trail = head; //set curr and trail at the start node

while (curr->next != NULL) { //for the rest of the elements in the list
if (curr->data > curr->next->data) { //compare curr and curr->next

temp = curr->next; //swap pointers for curr and curr->next
curr->next = curr->next->next;
temp->next = curr;

//now we need to setup pointers for trail and possibly head
if(curr == head) //this is the case of the first element swapping to preserve the head pointer
head = trail = temp;
else //setup trail correctly
trail->next = temp;
curr = temp; //update curr to be temp since the positions changed
}
//advance pointers
trail = curr;
curr = curr->next;
}
}
}

[/sourcecode]