Computers are good at performing repetitive tasks; doing the same boring nonsense over and over. Two great examples are searching and sorting.

In my C programming books, I demonstrate the most basic and obvious type of sorting technique: The bubble sort. It’s a brute-force method of comparing each item in a list to every other item in the list. Items out of place are swapped, and the whole process repeats.

For simple, small lists, the bubble sort works fine. I demonstrate such a sort in Chapter 12 of my book, Beginning Programming with C For Dummies. A sort of 40 random integers is presented as the solution for the book’s Exercise 12-14. It works well and demonstrates how a bubble sort works. And it’s pretty fast for sorting 40 values.

How about creating and sorting an array of 100,000 random integers?

A computer is quite content to sort 100,000 integers, although a bubble sort probably isn’t the most efficient way to order those values. (And at 4 bytes of storage per int, that’s nearly half a megabyte of data.)

The change to the source code for Exercise 12-14 is simple: Modify the SIZE constant, changing it from 40 to 100000. To make the code run faster, I removed the output statements; displaying output slows down any program, but more importantly watching 100,000 sorted, random integers fly up the terminal screen is meaningless.

Here is the final code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 100000

int main()
{
    int bubble[SIZE];
    int inner,outer,temp,x;

    srand((unsigned)time(NULL));
    /* populate array */
    for(x=0;x<SIZE;x++)
    {
        bubble[x] = rand();
        bubble[x] = (bubble[x] % 100)+1;
    }
    printf("%d element array created.\n",SIZE);

    /* bubble sort */
    printf("Sorting . . . ");
    for(outer=0;outer<SIZE-1;outer++)
    {
        for(inner=outer+1;inner<=SIZE;inner++)
        {
            if(bubble[outer] > bubble[inner])
            {
                temp=bubble[outer];
                bubble[outer] = bubble[inner];
                bubble[inner] = temp;
            }
        }
    }
    printf("Done!\n");

    return(0);
}

Compile and run the program to see how long your computer takes to do a bubble sort of 100,000 integers. On a Unix terminal (Mac OS X, Linux, or CYGWIN) use the time command, followed by the compiled program name, such as:

$ time blog0314

Assuming that blog0314 is the program generated by this Lesson’s source code, here’s the sample output on my screen:

100000 element array created.
Sorting . . . Done!

real	0m9.910s
user	0m9.899s
sys	0m0.011s

Nearly 10 seconds (9.910) elapsed between the time the first string was displayed and the program completed. That’s probably much faster than you (as a human) could sort the values, but it’s near an eternity for the computer. That’s because the bubble sort is inefficient.

Next week I’ll show you another way to sort that’s much, much faster. Or I should write, quicker.