MorkaLork Development

Interesting stuff I've picked up over the years...

BubbleSort

2009-09-15 10:32:51 | 505 views | bubblesort C# array

Prologue


Bubbelsort is one of the most basic sorting algorithms there is. This article will not go deep into the history of the bubblesort or even the uses of bubblesort. It will instead simply explain how the bubblesort technique works.

Allright...


Imagine a range of numbers, like this:
3, 2, 5, 1, 4

And then imagine the simplest way to sort these. It must be to check every number to it’s neighbor to the right. If the number is higher then switch them, like this:

3, 2, 5, 1, 4
Is 3 higher than two?
Yes, so switch them!

2, 3, 5, 1, 4
Is 3 higher than 5?
No, so don’t switch them

2, 3, 5, 1, 4
Is 5 higher than 1?
Yes, so switch them!

2, 3, 1, 5, 4
Is 5 higher than 4?
Yes so switch them!

2, 3, 1, 4, 5
Done!

Then we do this step 4 more times (once for every element in the collection), but the sorting in this case will actually be finished in just 3 attempts, not 5.
Here’s a list of all steps

A visual of how it works


The array


3, 2, 5, 1, 4

Step 1


Array Element to check Swap?
3, 2, 5, 1, 43Yes
2, 3, 5, 1, 43No
2, 3, 5, 1, 45Yes
2, 3, 1, 5, 45Yes
2, 3, 1, 4, 55Yes


Step 2


Array Element to check Swap?
2, 3, 1, 4, 52No
2, 3, 1, 4, 53Yes
2, 1, 3, 4, 53Yes
2, 1, 3, 4, 54No
2, 1, 3, 4, 55No


Step 3


Array Element to check Swap?
2, 1, 3, 4, 52Yes
1, 2, 3, 4, 52No
1, 2, 3, 4, 53No
1, 2, 3, 4, 54No
1, 2, 3, 4, 55No


As we can see, the algorithm is quite simple, it just looks to the right to see what’s there. If the element has a higher value it switches them. Now, you can see why this is not the best of sorting algorithms, it’s very basic and rather clumsy, it doesn’t know anything about the collection, just the two elements it’s currently “swapping”.
One pattern emerges as well; the more we sort, the less we swap. This also demonstrates the ineffectiveness of the algorithm.

C# approach


If you want to use this technique in C#, it’s very easy, all you need is a nested for-loop and a collection, in this case we’ll use integers:


using System;

namespace MorkaBubbleSort {
class Program {

static void Main(string[] args) {
//Our example array
int[] arr = new int[] { 3, 2, 5, 1, 4 };

Console.WriteLine("Unsorted:");
displayElements(arr);

sort(arr);

Console.WriteLine("Sorted:");
displayElements(arr);

Console.Read();
}

static void displayElements(int[] arr) {
foreach (int i in arr) {
Console.Write("{0, -3}", i);
}
Console.Write("\n");
}

static void sort(int[] arr) {
int temp;
//Start from the end and move backwards
for (int outer = arr.Length - 1; outer >= 1; outer--) {
//Start from the beginning, but only go as far as to the current outer element
for (int inner = 0; inner <= outer - 1; inner++) {
//Only swap if the current number to check is larger
//than its element to the right
if (arr[inner] > arr[inner + 1]) {
//We'll save the number we're checking
temp = arr[inner];
//We'll add the number to the right to the current number
arr[inner] = arr[inner + 1];
//We place the number we are checking to the right,
//thus ending the swap
arr[inner + 1] = temp;
}
}
}
}
}
}


And the end result will look like this:
The result of the bubblesort, displayed in console


Article comments

Feel free to comment this article using a facebook profile.

I'm using facebook accounts for identification since even akismet couldn't handle all the spam I receive every day.