8.5. Linked List Bubble Sort¶
8.5.1. Non-recursive Bubble Sort¶
The bubble sort algorithm is normally implemented with data in an array. It starts at the end of the data and swaps adjacent items if the later item is smaller than the earlier item. It then moves one item up in the data and repeats the operation. So the smaller items “bubble up” towards the front of the data while the larger items fall towards the bottom of the data. The algorithm is finished when it can pass through the data from end to first without swapping any values.
As stated, a bubble sort could be implemented with data in double linked list, or with a single linked list by reversing the algorithm to push larger items down the data rather than bubbling the smaller items up through the data. Here is an example including the code to test the sort function.
#include <stdio.h>
#include <stdlib.h>
typedef struct list {
int data;
struct list *next;
} LIST;
LIST *append( LIST *, int );
LIST *sort( LIST * );
LIST *list_switch( LIST *, LIST * );
void print_list( LIST * );
int main(void)
{
LIST *try;
int i;
// This is just testing code
try = NULL;
try = append( try, 5 );
try = append( try, 2 );
try = append( try, 9 );
try = append( try, 8 );
try = append( try, 1 );
try = append( try, 7 );
printf("Original list:\n");
print_list( try );
try = sort( try );
printf("Sorted list:\n");
print_list( try );
return 0;
}
void print_list( LIST *t )
{
while( t != NULL ) {
printf( "%d\n", t->data );
t = t->next;
}
}
LIST *append( LIST *start, int newdata )
{
LIST *new, *end, *ret;
if( (new = (LIST *)malloc(sizeof(LIST))) == NULL) {
fprintf( stderr, "Memory Allocation error.\n" );
// In Windows, replace following with a return statement.
exit(1);
}
if( start == NULL )
ret = new;
else {
ret = start;
end = start;
while( end->next != NULL ) end = end->next;
end->next = new;
}
new->data = newdata;
new->next = NULL;
return ret ;
}
LIST *sort( LIST *start )
{
LIST *p, *q, *top;
int changed = 1;
/*
* We need an extra item at the top of the list just to help
* with assigning switched data to the 'next' of a previous item.
* It (top) gets deleted after the data is sorted.
*/
if( (top = (LIST *)malloc(sizeof(LIST))) == NULL) {
fprintf( stderr, "Memory Allocation error.\n" );
// In Windows, replace following with a return statement.
exit(1);
}
top->next = start;
if( start != NULL && start->next != NULL ) {
/*
* This is a survival technique with the variable changed.
*
* Variable q is always one item behind p. We need q, so
* that we can make the assignment q->next = list_switch( ... ).
*/
while( changed ) {
changed = 0;
q = top;
p = top->next;
while( p->next != NULL ) {
/* push bigger items down */
if( p->data > p->next->data ) {
q->next = list_switch( p, p->next );
changed = 1;
}
q = p;
if( p->next != NULL )
p = p->next;
}
}
}
p = top->next;
free( top );
return p;
}
LIST *list_switch( LIST *l1, LIST *l2 )
{
l1->next = l2->next;
l2->next = l1;
return l2;
}
Here is what the above program prints when it runs.
Original list:
5
2
9
8
1
7
Sorted list:
1
2
5
7
8
9
8.5.2. Recursive Bubble Sort¶
A recursive version of bubble sort can follow the traditional algorithm of starting at the end of the data. One difference between the traditional bubble sort algorithm is that here, once a swap is done, we start over at the end of the data. Here, we begin and by pushing the larger items towards the end of the list as the recursive function calls cause us to move to the end of the list. We compare and possibly swap the first and second values of the list if a smaller item has come to be in second position. After a swap, we must re-sort from the second item to the end of the list.
LIST *sort( LIST *start )
{
if( start == NULL ) return NULL;
/* First push the larger items down */
if( start->next !=NULL && start->data > start->next->data )
start = list_switch( start, start->next );
/* Always sort from second item on */
start->next = sort(start->next);
/* bubble smaller items up */
if( start->next !=NULL && start->data > start->next->data ) {
start = list_switch( start, start->next );
start->next = sort(start->next);
}
return start;
}
LIST *list_switch( LIST *l1, LIST *l2 )
{
l1->next = l2->next;
l2->next = l1;
return l2;
}
8.5.3. Improved Recursive Bubble Sort¶
A performance problem with the above algorithm is that we start over again after each data swap. (Notice that sort() can be called twice within the recursive function.) This is because the data swap is limited to swapping adjacent items. The following example borrows from Sorted Insert To a List and thus does not need to start the algorithm over again after each data swap.
LIST *sort( LIST *start )
{
if( start == NULL ) return NULL;
start->next = sort(start->next);
if( start->next != NULL && start->data > start->next->data ) {
start = move( start );
}
return start;
}
/*
* The following function moves the top item in the linked list
* to its correct position. This is similar to insertion sort.
* The item that was the second item in the list becomes the
* top item. The list should contain at least 2 items and
* from the second item on, the list should already be sorted.
*/
LIST *move( LIST *x )
{
LIST *n, *p, *ret;
p = x;
n = x->next;
ret = n;
while( n != NULL && x->data > n->data ) {
p = n;
n = n->next;
}
/* we now move the top item between p and n */
p->next = x;
x->next = n;
return ret;
}
8.5.4. Quick sort¶
The quick sort algorithm is considered the fastest sorting algorithm, and the standard C library includes a quick sort function (qsort) but it works on arrays, not linked lists. However, we can build an array holding pointers to successive items in a linked list, use the qsort function and then rebuild the linked list from the array of sorted pointers.
We leave this as a exercise for the student.
