By Dan Gookin

With C programming, computers are designed to quickly and merrily accomplish boring tasks, such as sorting an array. In fact, they love doing it so much that “the sort” is a basic computer concept upon which many theories and algorithms have been written. It’s a real snoozer topic if you’re not a Mentat or a native of the planet Vulcan.

The simplest sort is the bubble sort, which not only is easy to explain and understand but also has a fun name. It also best shows the basic array-sorting philosophy, which is to swap values between two elements.

Suppose that you’re sorting an array so that the smallest values are listed first. If array[2] contains the value 20, and array[3] contains the value 5, these two elements would need to swap values. To make it happen, you use a temporary variable in a series of statements that looks like this:

temp=array[2]; /* Save 20 in temp */
array[2]=array[3]; /* Store 5 in array[2] */
array[3]=temp; /* Put 20 in array[3] */

In a bubble sort, each array element is compared with every other array element in an organized sequence. When one value is larger (or smaller) than another, the values are swapped. Otherwise, the comparison continues, plodding through every possible permutation of comparisons in the array. A Bubble Sort demonstrates.

A BUBBLE SORT

#include <stdio.h>
#define SIZE 6
int main()
{
 int bubble[] = { 95, 60, 6, 87, 50, 24 };
 int inner,outer,temp,x;
/* Display original array */
 puts("Original Array:");
 for(x=0;x<SIZE;x++)
 printf("%dt",bubble[x]);
 putchar('n');
/* Bubble sort */
 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;
 }
 }
 }
/* Display sorted array */
 puts("Sorted Array:");
 for(x=0;x<SIZE;x++)
 printf("%dt",bubble[x]);
 putchar('n');
 return(0);
}

A Bubble Sort is long, but it’s easily split into three parts, each headed by a comment:

  • Lines 10 through 14 display the original array.

  • Lines 16 through 28 sort the array.

  • Lines 30 through 34 display the sorted array (duplicating Lines 10 through 14).

The constant SIZE is defined in Line 3. This directive allows you to easily change the array size in case you reuse this code again later (and you will).

The sort itself involves nested for loops: an outer loop and an inner loop. The outer loop marches through the entire array, one step at a time. The inner loop takes its position one element higher in the array and swoops through each value individually.

Exercise 1: Copy the source code from A Bubble Sort into your editor and create a new project, ex1213. Build and run.

Exercise 2: Using the source code from A Bubble Sort as a starting point, create a program that generates 40 random numbers in the range from 1 through 100 and stores those values in an array. Display that array. Sort that array. Display the results.

Exercise 3: Modify the source code from Exercise 2 so that the numbers are sorted in reverse order, from largest to smallest.

Exercise 4: Write a program that sorts the text in the 21-character string “C Programming is fun!”