# 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

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.

## 5 thoughts on “The Notorious Bubble Sort”

1. 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?

• 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!

• > 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.

• 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. 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