The Magic of Bubble Sort – Practicing Literate Programming

Some Sort of Bubble Sorting

Most programs will start with included headers and global variables.
This is because compilers understand source code in a particular way.
However, since this article is meant to be read by humans, I’d like
to start with the most important part of our program.

Sorting is what this is all about, so we shall start with a simple sorting
algorithm. I believe this one is called bubble sort. We’ll compare each
adjacent integer in the list and ‘bubble up’ the largest.

<Bubble Sort>=
if(idx > 1) {
    int tmp;

    int swapped = 1;
    while(swapped) {
        swapped = 0;
        for(int i = 0; i < (idx-1); i++) {
            if(arr[i] > arr[i+1]) {
                swapped = 1;
                <Swap>
            }
        }
    }
}

To make the code a bit more readable, let’s take out the swap procedure.

<Swap>=
tmp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = tmp;

Include required headers here.

<Included Headers>=
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

For simplicity’s sake, we assume a maximum of 100 integers to be sorted.
We also use two arrays here for simplicity. One array to store the input,
and a second to store the sorted values.

Oh, and we will track the size of each array using a couple index variables.

<Global Variables>=
#define max_nums 100
int idx = 0, sorted_idx = 0;
int arr[max_nums];
int sorted[max_nums];

Use a simple procedure to print stored integers for testing.

<Print Stored Ints>=
printf("Stored Ints: ");
for(int i = 0; i < (idx-1); i++) {
    printf("%d, ", arr[i]);
}
printf("%d\n", arr[idx-1]);

We will iterate over the input array in order to store the list of integers.

<Store Input>=
char *input_string = args[1];
char *string = input_string;
int len = strlen(input_string);
for(int i = 0; idx < max_nums, i < len; i++) {
    if(input_string[i] == ',') {
        input_string[i] = 0;
        arr[idx++] = atoi(string);
        string = &input_string[i+1];
    }

    if(i == (len-1)){
        arr[idx++] = atoi(string);
    }
}

And now, we put the entire program together. Input will be assumed as
a comma-separated list of integers.

<Full Program>=
<Included Headers>

<Global Variables>

int main(int argc, char **args)
{
    if(argc < 2) {
        fprintf(stderr, "Pass in a comma-separated string of integers.\n");
        return 1;
    }

    <Store Input>

    printf("\nBEFORE SORTING:\n");
    <Print Stored Ints>

    <Bubble Sort>

    printf("\nAFTER SORTING:\n");
    <Print Stored Ints>

    return 0;
}

Leave a Reply

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