The Notorious Bubble Sort in C

I am sticking my neck out here by implementing the notorious Bubble Sort in C. There are many sorting algorithms and even more variations on a theme, but the bubble sort is probably the best known. It's simple to understand and the process can be illustrated with some cute animations and even Hungarian folk dancing!

Despite all that the bubble sort cannot claim to be the most efficient, and is often derided. However, it is still taught and sometimes crops up in coding tests or interview questions so for that reason I'll put together a simple implementation. For the full lowdown take a look at the Wikipedia article.

Bubble Sort on Wikipedia

And then take a look at the Hungarian folk dancers.

Bubble-sort with Hungarian folk dance

Hopefully Wikipedia and Youtube were enlightening enough so let's get coding.

Swapping Integers Using Exclusive Or

Bubble Sort relies on being able to swap two values, and the most obvious way of doing this is by using a temporary variable, for example

Swapping using temporary variable

int a = 45;
int b = 99;
int temp;

temp = a; // temp = 45
a = b; // a = 99
b = temp; // b = 45

However, if we are swapping integers (or C chars) we can use a trick with XOR, the symbol for which in C is ^. The following code and comments show how this works. Pay particular attention to the binary values in the comments.

Swapping using exclusive or

int a = 45; // 00101101
int b = 99; // 01100011
a = a ^ b;  // 01001110
b = a ^ b;  // 00101101
a = a ^ b;  // 01100011

I think this is a neat and clever bit of code so I'll be using it in this project.

Coloured Text in the Linux Terminal

If you sneak a look at the program's output at the bottom of the page you'll see I have colour-coded the sorted and unsorted parts of the array. I borrowed this technique from something I found on stackoverflow - take a look at the item here.

Implementing Bubble Sort in C

Create a new folder and within it create the following empty files:

  • main.c
  • bubblesort.h
  • bubblesort.c

Source Code Links

ZIP File
GitHub

Open bubblesort.h and paste in the following code. You can download the source code as a zip or clone/download from Github if you prefer.

bubblesort.h

//--------------------------------------------------------
// FUNCTION PROTOTYPES
//--------------------------------------------------------
void bubblesort(int* array, int size);
void printarray(int* array, int size, int sortedto);

That's the header file completed, so now we'll do the main function. In main.c paste the following.

main.c

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

#include"bubblesort.h"

//--------------------------------------------------------
// FUNCTION main
//--------------------------------------------------------
int main()
{
    puts("-----------------");
    puts("| codedrome.com |");
    puts("| Bubble Sort   |");
    puts("-----------------\n");

    int size = 16;

    int* data = malloc(size * sizeof(int));

    srand(time(NULL));

    for(int i = 0; i < size; i++)
    {
        data[i] = (rand() % 128);
    }

    bubblesort(data, size);

    free(data);

    return EXIT_SUCCESS;
}

In main we use malloc to get enough memory for 16 ints (not forgetting to call free at the end) and then initialize them to random values between 0 and 128. We then call the bubblesort function which will be implemented next.

Open bubblesort.c and paste in the following.

bubblesort.c

#include<stdio.h>

#include"bubblesort.h"

#define RED "\x1B[31m"
#define GRN "\x1B[32m"
#define RESET "\x1B[0m"

//--------------------------------------------------------
// FUNCTION bubblesort
//--------------------------------------------------------
void bubblesort(int* array, int size)
{
    puts("Unsorted...");
    printarray(array, size, size);

    puts("Bubble Sorting...");

    int lastindex = size - 2;
    int index;

    while(lastindex >= 0)
    {
        for(index = 0; index <= lastindex; index++)
        {
            if(array[index] > array[index+1])
            {
                array[index] = array[index] ^ array[index+1];
                array[index+1] = array[index] ^ array[index+1];
                array[index] = array[index] ^ array[index+1];
            }
        }

        printarray(array, size, lastindex);

        lastindex--;
    }

    puts("Sorted!");
}
//--------------------------------------------------------
// FUNCTION printarray
//--------------------------------------------------------
void printarray(int* array, int size, int sortedto)
{
    for(int i = 0; i < size; i++)
    {
        if(i > sortedto)
            printf(GRN "%3d " RESET, array[i]);
        else
            printf(RED "%3d " RESET, array[i]);
    }

    printf("\n");
}

Note that we #define the colours used in the output.

The bubblesort function takes an int array (specifically an int pointer) to sort, and the size of the array, and starts off by printing the array as it is. When sorting we only need to go up to the last but one unsorted item, which is compared to the last unsorted item and swapped if necessary. The index of this item is stored in the lastindex variable.

We now enter a while loop. At the end of this loop lastindex is decremented, and the loop's condition is that we have not yet got down to 0.

For each iteration of the outer while loop we for-loop through the unsorted data, swapping any items which are out of order using the xor trick described above. For each iteration of the while loop we call the printarray function to show the state of the array at that point in time, including the colour coding.

That's the source code finished so we can compile and run it. In the terminal type the following

Compiling

gcc main.c bubblesort.c -std=c11 -lm -o bubblesort

and then run it with

Running

./bubblesort

This is the output from the program. Each row represents the data after one iteration, with unsorted data shown in red and sorted data shown in green. You can easily see that after each pass one more item has bubbled up to the top.

Program Output

-----------------
| codedrome.com |
| Bubble Sort   |
-----------------

Unsorted...
 93  48  69  12 116   5  22   1  94 101   8  57  72 102  64  25
Bubble Sorting...
 48  69  12  93   5  22   1  94 101   8  57  72 102  64  25 116
 48  12  69   5  22   1  93  94   8  57  72 101  64  25 102 116
 12  48   5  22   1  69  93   8  57  72  94  64  25 101 102 116
 12   5  22   1  48  69   8  57  72  93  64  25  94 101 102 116
  5  12   1  22  48   8  57  69  72  64  25  93  94 101 102 116
  5   1  12  22   8  48  57  69  64  25  72  93  94 101 102 116
  1   5  12   8  22  48  57  64  25  69  72  93  94 101 102 116
  1   5   8  12  22  48  57  25  64  69  72  93  94 101 102 116
  1   5   8  12  22  48  25  57  64  69  72  93  94 101 102 116
  1   5   8  12  22  25  48  57  64  69  72  93  94 101 102 116
  1   5   8  12  22  25  48  57  64  69  72  93  94 101 102 116
  1   5   8  12  22  25  48  57  64  69  72  93  94 101 102 116
  1   5   8  12  22  25  48  57  64  69  72  93  94 101 102 116
  1   5   8  12  22  25  48  57  64  69  72  93  94 101 102 116
  1   5   8  12  22  25  48  57  64  69  72  93  94 101 102 116
Sorted!

As I mentioned earlier bubble sort is rather inefficient, and this project is intended only as a demonstration and programming exercise. You might find the xor swap and terminal colours more useful than the algorithm itself!

If you actually need to sort an array in production code you should look first at the C standard library's qsort (Quicksort) function, and I'll write a post on using this soon.