SORTER

The source code for sorter.c may be downloaded. The purpose of this program is to demonstrate a bubble sort which sorts the values in an array of four items into ascending order (smallest value at item[0] an largest item[3]).

The sort works in a number of "passes". In each pass the program checks every consecutive value in the entire array (3 checks in an array of four items). If any value is found out of order, it is swapped with the previous value (see also the swap example). At the start of each pass, a variable "sorted" is set to 1. If at any time during the pass a value is swapped, the variable sorted is reset to 0.

At the end of each pass, the variable sorted is checked. If it is found to be zero, the array may not yet be sorted, and another pass is commenced. If it is set to 1, the array must now be sorted, since it is known that every item has been checked and found to be order.

This types of sort is known as a bubble sort because the values in the array "bubble" upwards towards the correct value, rather like bubbles rising in a pond. The algorithm is efficient when the original data is very mis-ordered. If only some values are out of place, a more efficient algorithm is known as a "shuttle interchange" sort. Sorting is a common computer task and many sophisticated algorithms exist.

You type> cat sorter.c
void swap(int *a, *b)
       // variables int t *a,*b;
{       int c;
        c  =*a;
        *a =*b;
        *b =c;
        return;
}
main()
{       int count;                      /* a counter */
        int sorted;                     /* a flag */
        int item[4];
        item[0]=1;item[1]=2;
        item[2]=0;item[3]=3;
        /* print the initial value of the array */
        count = 3;
init_loop:
        printf("item[%d] == %d\n",count,item[count]);
        count--;
        if (count>=0) {goto init_loop;}
loop:   /* start of a pass through list of items */
        count = 3;      /* sort 4 items in a list */
        sorted = 1;                     /* assume sorted */
        printf("\nStarting a new pass:\n");
next:   if(item[count] < item[count-1]){
                swap(item+count,item+(count-1));
                sorted=0;               /* was not sorted */
        }
        printf("item[%d] == %d\n",count,item[count]);
        count--;
        if(count > 0){ goto next;}
        printf("item[%d] == %d\n",count,item[count]);
        if(sorted != 1) { goto loop;}
}
you type> cc -o sorter sorter.c
you type> sorter
item[3] == 3
item[2] == 0
item[1] == 2
item[0] == 1
Starting a new pass:
item[3] == 3
item[2] == 2
item[1] == 1
item[0] == 0
Starting a new pass:
item[3] == 3
item[2] == 2
item[1] == 1
item[0] == 0

BACK to index page.