BubbleSort
Written by: maffelu , 2009-09-15 10:32:51
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, 4 | 3 | Yes |
| 2, 3, 5, 1, 4 | 3 | No |
| 2, 3, 5, 1, 4 | 5 | Yes |
| 2, 3, 1, 5, 4 | 5 | Yes |
| 2, 3, 1, 4, 5 | 5 | Yes |
Step 2
| Array | Element to check | Swap? |
|---|---|---|
| 2, 3, 1, 4, 5 | 2 | No |
| 2, 3, 1, 4, 5 | 3 | Yes |
| 2, 1, 3, 4, 5 | 3 | Yes |
| 2, 1, 3, 4, 5 | 4 | No |
| 2, 1, 3, 4, 5 | 5 | No |
Step 3
| Array | Element to check | Swap? |
|---|---|---|
| 2, 1, 3, 4, 5 | 2 | Yes |
| 1, 2, 3, 4, 5 | 2 | No |
| 1, 2, 3, 4, 5 | 3 | No |
| 1, 2, 3, 4, 5 | 4 | No |
| 1, 2, 3, 4, 5 | 5 | No |
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:
There are no comments on this article.
Leave a message!
If you have any question or just want to leave a message, just fill out the form below!
Your e-mail will not be visible in your post, it is for validation reasons only
Maffelu