Mailing List Articles Atom Feed Comments Atom Feed Twitter Reddit Facebook

Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blog bookmarklet booting bug hunting c sharp c++ challenge chrome os code codepen coding conundrums coding conundrums evolved command line compilers compiling compression css dailyprogrammer data analysis debugging demystification distributed computing documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro network networking nibriboard node.js operating systems own your code performance photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit redis reference releases resource review rust searching secrets security series list server software sorting source code control statistics storage svg talks technical terminal textures thoughts three thing game three.js tool tutorial twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 xmpp xslt

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,
    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

        passes++; //debug

    } while (!issorted);

    Console.WriteLine("Sorting Complete!");
    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!
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.

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



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.

First Impressions: C♯

I will be learning C♯ over the next year or so, and since I am almost a week into learning it, I thought that I would post my first impressions here on this blog.

C♯ is a compiled language developed by Microsoft that looks a little bit javascript, and a little bit like Rust (If you haven't heard of rust yet, I have written up a first impressions post here). Like rust, it has a type system, so you can't set a variable with the type int to a string. This type system is not a confusing, though, since it only has a single type for strings (rust has two - one that you can change and one that you can't) and you can convert between the different types quite easily (e.g. int.Parse() converts a string to an int).

The brackets syntax is almost identical to that of Javascript, except C♯ has classes and namespacees too (I don't really know what those do yet). Indentation also seems to be fairly important, which is perfectly fine by me since it improves the readability of your code.

Looking around on the internet, it seems that C♯ is tied in with Visual Studio quite closely. This might cause problems in the future, because I don't really want ot install visual studio (express) on my computer because of it's file size (the installer alone is > 600MB!). Hopefully I can continue to use the csc C♯ compiler I found in the .NET 4.0 folder on my computer as my code becomes more complex.

All in all C♯ looks like a good introductory language to the world of compiled programming. The syntax is straight forward and easy to understand so far, and it is kind of similar to Javascript, which eases the learning process considerably.

Art by Mythdael