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 WikipediaAnd then take a look at the Hungarian folk dancers.
Bubble-sort with Hungarian folk danceHopefully 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
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.