C Program: Bubble/Sinking Sort

Bubble Sort (or Sinking Sort) is a sorting agorithm which sorts numbers by repeatedly comparing two consecutive pair and swapping them if they are in incorrect order.

Consider the following unsorted set of numbers:

( 7 3 5 -9 )

We will illustrate the use of Bubble Sort to reorder them in ascending order, which will result in the set being sorted as follows.

( -9 3 5 7 )

First Iteration

The first number (from the left) is hooked. Comparison starts with the next adjacent number, and the next, till the last number is reached, exchanging places whenever the other number is smaller.

( 7 3 5 -9 ) → ( 3 7 5 -9 ), compare the first two elements; swaps since 7 > 3

( 3 7 5 -9 ) → ( 3 7 5 -9 ), no swap since 3 < 5

( 3 7 5 -9 ) → ( -9 7 5 3 ), swap since 3 > -9.

Second Iteration

The second number is fixed. Comparison starts with the next adjacent number till the last, exchanging places whenever the other number is smaller.

( -9 7 5 3 ) → ( -9 5 7 3 ), swap since 7 > 5

( -9 5 7 3 ) → ( -9 3 7 5 ), no swap since 5 > 3

Third Iteration

The third number is fixed. Comparison starts with the next adjacent number, which is the last. Since the other number is smaller, swapping takes place. This becomes the last iteration of the algorithm.

( -9 3 7 5 ) → ( -9 3 5 7 ), swap since 7 > 5

After this third iteration (which is based on the array size), we get our sorted array as:

( -9 3 5 7 )

The below C program illustrates the above sorting algorithm we performed.

The set ( -9 3 5 7 ) is assigned to the array numbers[] of type int. A third variable called temp is also used to temporarily store assigned numbers while swapping. 

				
				#include <stdio.h>
				int main() {
					int numbers[] ={7,3,5,-9}, temp;
					unsigned short int i, j, n;
					// the size of given array
					n = 4;
					// bubble sort
					for(i = 0; i < (n-1); i++) {
						for(j = i+1; j < n; j++) {
							if(numbers[i] > numbers[j]) {
								temp = numbers[j];
								numbers[j] = numbers[i];
								numbers[i] = temp;
							}
						}
					}
					// printing the sorted array
					for(i = 0; i < n; i++) {
						printf("%d ", numbers[i]);
					}
					return 0;
				}

With Array Input

Instead of feeding hard-coded set of numbers, we can enhance the above C program to read numbers dynamically. The size of the array numbers[] is restricted to just 100, but there is a much better approach by using dynamic memory allocation, which we will cover in other example programs. 

					
					#include <stdio.h>
					int main() {
						int numbers[100], temp;
						unsigned short int i, j, n;
						printf("Enter the dimension of the array: ");
						scanf("%hu", &n);
						// array input
						for(i = 0; i < n; i++) {
							printf("Enter numbers[%hu]: ", i);
							scanf("%d", &numbers[i]);
						}
						// bubble sort
						for(i = 0; i < (n-1); i++) {
							for(j = i+1; j < n; j++) {
								if(numbers[i] > numbers[j]) {
									temp = numbers[j];
									numbers[j] = numbers[i];
									numbers[i] = temp;
								}
							}
						}
						// printing the sorted array
						for(i = 0; i < n; i++) {
							printf("%d ", numbers[i]);
						}
						return 0;
					}

Practically, Bubble Sort is not recommended for sorting. Insertion Sort, which has the same complexity order of $\text{O}(n^{2})$ as Bubble Sort, is much efficient when compared to it.