The Notorious Bubble Sort

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

Open bubblesort.h and paste in the following code. You can download the source code from the Downloads page 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("-----------------\n| code-in-c.com |\n| Bubble Sort |\n-----------------\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

-----------------
| code-in-c.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. I'll be implementing my own Quicksort in a later post along with various other sorting algorithms, but in the meantime please post any thoughts or suggestions you might have in the comments below.

Please follow Code in C on Twitter to keep up to date with new posts.

This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to The Notorious Bubble Sort

  1. boomslang says:

    To be pedantic, the exclusive-or trick for swapping can be used on any integral type, which as of C ’89 is:
    char
    unsigned char
    int
    unsigned int // or just, unsigned
    long int
    unsigned long int
    bit fields also are integral types

    The ’89 C standard is a bit ambiguous about long long int’s, referring to them as arithmetic types. I couldn’t find any clarification in the C ’99 standard (doesn’t mean it’s not there, I just couldn’t find it). Can anyone out there clarify this for me?

    • Chris Webb says:

      Thanks for your comment. You are right of course, apologies if I gave the impression it only works with int or char.

      Not sure about long long, which it seems could be implemented with more than 64 bits. Needs more research and experimentation!

      • boomslang says:

        > apologies if I gave the impression it only works with int or char.

        No worries, you didn’t give that impression, and the way you used it is correct given your clearly-defined constraints of your program.

        I just ran a comparison of the XOR approach and the temp approach to swapping on my machine, Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz.

        $ gcc –version
        gcc (GCC) 7.1.1 20170528
        Copyright (C) 2017 Free Software Foundation, Inc.
        This is free software; see the source for copying conditions.

        I ran 100,000,000 swaps using each approach with the ‘time’ command. The averages are of three runs each:

        (using XOR swap)
        real 0m0.310s
        user 0m0.300s

        (using temp variable for swap)
        real 0m0.256s
        user 0m0.250s
        sys 0m0.000s

        It’s not the first time I’ve found that the compiler beats me (as a programmer). Again, this is only the results from my laptop and of course they will vary with hardware/compiler version.

        • Chris Webb says:

          Interesting. I’ll try that when I’ve got time with -save-temps and look at the assembly to see what it’s doing.

          I’m planning on doing a post about squeezing the maximum efficiency out of C using register, inline, compiler options and anything else I can think of.

  2. boomslang says:

    I’ll let you look at the assembly on your own because you prob have a different setup than me anyway. On my side, the XOR approach uses a lot more mov instructions to set up for the xor instructions. The temp version uses fewer mov instructions so it wins performance in that area.

    Maybe the XOR approach written by hand in assembly could be faster but I’ll leave that as an exercise for the reader. The way I wrote the functions is the same as you have at the top of the post.

    0000000000400500 :
    400500: 55 push %rbp
    400501: 48 89 e5 mov %rsp,%rbp
    400504: 48 89 7d f8 mov %rdi,-0x8(%rbp)
    400508: 48 89 75 f0 mov %rsi,-0x10(%rbp)
    40050c: 48 8b 45 f8 mov -0x8(%rbp),%rax
    400510: 8b 10 mov (%rax),%edx
    400512: 48 8b 45 f0 mov -0x10(%rbp),%rax
    400516: 8b 00 mov (%rax),%eax
    400518: 31 c2 xor %eax,%edx
    40051a: 48 8b 45 f8 mov -0x8(%rbp),%rax
    40051e: 89 10 mov %edx,(%rax)
    400520: 48 8b 45 f8 mov -0x8(%rbp),%rax
    400524: 8b 10 mov (%rax),%edx
    400526: 48 8b 45 f0 mov -0x10(%rbp),%rax
    40052a: 8b 00 mov (%rax),%eax
    40052c: 31 c2 xor %eax,%edx
    40052e: 48 8b 45 f0 mov -0x10(%rbp),%rax
    400532: 89 10 mov %edx,(%rax)
    400534: 48 8b 45 f8 mov -0x8(%rbp),%rax
    400538: 8b 10 mov (%rax),%edx
    40053a: 48 8b 45 f0 mov -0x10(%rbp),%rax
    40053e: 8b 00 mov (%rax),%eax
    400540: 31 c2 xor %eax,%edx
    400542: 48 8b 45 f8 mov -0x8(%rbp),%rax
    400546: 89 10 mov %edx,(%rax)
    400548: 90 nop
    400549: 5d pop %rbp
    40054a: c3 retq

    000000000040054b :
    40054b: 55 push %rbp
    40054c: 48 89 e5 mov %rsp,%rbp
    40054f: 48 89 7d e8 mov %rdi,-0x18(%rbp)
    400553: 48 89 75 e0 mov %rsi,-0x20(%rbp)
    400557: 48 8b 45 e8 mov -0x18(%rbp),%rax
    40055b: 8b 00 mov (%rax),%eax
    40055d: 89 45 fc mov %eax,-0x4(%rbp)
    400560: 48 8b 45 e0 mov -0x20(%rbp),%rax
    400564: 8b 10 mov (%rax),%edx
    400566: 48 8b 45 e8 mov -0x18(%rbp),%rax
    40056a: 89 10 mov %edx,(%rax)
    40056c: 48 8b 45 e0 mov -0x20(%rbp),%rax
    400570: 8b 55 fc mov -0x4(%rbp),%edx
    400573: 89 10 mov %edx,(%rax)
    400575: 90 nop
    400576: 5d pop %rbp
    400577: c3 retq

Leave a Reply

Your email address will not be published. Required fields are marked *