Reverse Bubble Sorting

We had our second algorithms lecture this week - this time is was on bubble sorting. Apparently we will be doing several sorting algorithms over the next few weeks, each with their own strengths and weaknesses.

Today I bring you an optimised bubble sort implementation in C♯! This will be the first C♯ code that I have posted on this blog.

Basically, the bubble sort algorithm iterates over an array of numbers repeatedly and swaps those that are in the wrong order, until there aren't any more numbers left to swap.

Here is the script:

static void DoBubbleSort(int[]arraytosort) {
    int endingpoint = 1,
        temp;
    bool issorted;

    int swaps = 0,
        iterations = 0,
        passes = 0; //debug

    do {
        issorted = true;

        for(int i = arraytosort.Length - 1; i >= endingpoint; i--)
        {
            iterations++; //debug
            //Console.WriteLine("i: " + i + " i-1: " + (i - 1));

            if (arraytosort[i - 1] > arraytosort[i])
            {
                swaps++; //debug
                //swap the numbers around
                temp = arraytosort[i - 1];
                arraytosort[i - 1] = arraytosort[i];
                arraytosort[i] = temp;

                issorted = false;
            }
        }

        Console.Write("pass: " + passes + " ");
        printarray(arraytosort); //debug
        Console.WriteLine();

        passes++; //debug

        endingpoint++;
    } while (!issorted);

    Console.WriteLine("Sorting Complete!");
    Console.WriteLine("Statistics\n----------");
    Console.WriteLine("Passes: " + passes + ", Iterations: " + iterations + " Swaps: " + swaps);
}

...and here is an example of what it outputs:

Original: [66, 51,  0,  5, 42, 92,  8,  8, 28,  8]
pass: 0 [ 0, 66, 51,  5,  8, 42, 92,  8,  8, 28]
pass: 1 [ 0,  5, 66, 51,  8,  8, 42, 92,  8, 28]
pass: 2 [ 0,  5,  8, 66, 51,  8,  8, 42, 92, 28]
pass: 3 [ 0,  5,  8,  8, 66, 51,  8, 28, 42, 92]
pass: 4 [ 0,  5,  8,  8,  8, 66, 51, 28, 42, 92]
pass: 5 [ 0,  5,  8,  8,  8, 28, 66, 51, 42, 92]
pass: 6 [ 0,  5,  8,  8,  8, 28, 42, 66, 51, 92]
pass: 7 [ 0,  5,  8,  8,  8, 28, 42, 51, 66, 92]
pass: 8 [ 0,  5,  8,  8,  8, 28, 42, 51, 66, 92]
Sorting Complete!
Statistics
----------
Passes: 9, Iterations: 45 Swaps: 24

The script keeps track of the furthest point in the array it reached on each pass and goes one less each time - this is because the smallest number will always get pushed into its proper place at the left hand side on each pass.

As for the reason the script iterates backwards, in Javascript it is recommended that you iterate backwards to avoid repeatedly referencing Array.length, since it has to count the contents of an array upon each refernce. This is probably not the case with C♯, but it is a habit of mine :)

It is important to note that even though the function doesn't return anything, it still sorts the array because arrays are passed by reference by default, just like in Javascript (aka Ecmascript).

There are quite a few debug statements in there. Remove then for actual use in your code.

• Full Code: http://pastebin.com/K6Wpy2T8
• DoBubbleSort function only: http://pastebin.com/Z7PEmzej
• DoBubbleSort function without debug statements: http://pastebin.com/h1UFv28m

A (64 bit) compiled version of the script is available:

reversebubblesort.exe

Hashes:

Algorithm	Hash
CRC32	644f6c6a
MD5	93fba7a072954ee6f34fcf44913eadc7
SHA1	01a54b24c475ec2ff1bf159dc1224e10553f430d
SHA-256	d32d689e2785d738c54e43a9dc70c1d8f2de76383022a87aa4f408519a7941cb
SHA-384	df7c4ac441aabaa1f182ade7532885d8ee5518c26f17d72d7952dcfaa39552dda9ad219a37661591fea169fd6ed514bb
SHA-512	c993509901bb65cd893d1c8455c5ad8dc670632e5476aad899980348b45bc3435cfab3fe6d8fd80606cfea3608770c9900be51e09f6f1a8c9fd5fe28169fd81d

Remember to always verify the integrity of your downloaded files, especially the larger ones. If you would like another type of binary (e.g. 32 bit, ARM, etc.), please post a comment below and I will reply with a download link. The compiler used was csc.exe on a Windows 7 64 bit command line.

Questions and / or comments are welcome below.