Bubble sort is one of the simplest sorting algorithm but if you ask anyone to implement on the spot it gives you an opportunity to gauge programming skills of a candidate.

Let us take the array of numbers “5 1 4 2 8″, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in **bold** are being compared. Three passes will be required.

**First Pass:**

( **5** **1** 4 2 8 ) ( **1** **5** 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 **5** **4** 2 8 ) ( 1 **4** **5** 2 8 ), Swap since 5 > 4

( 1 4 **5** **2** 8 ) ( 1 4 **2** **5** 8 ), Swap since 5 > 2

( 1 4 2 **5** **8** ) ( 1 4 2 **5** **8** ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

**Second Pass:**

( **1** **4** 2 5 8 ) ( **1** **4** 2 5 8 )

( 1 **4** **2** 5 8 ) ( 1 **2** **4** 5 8 ), Swap since 4 > 2

( 1 2 **4** **5** 8 ) ( 1 2 **4** **5** 8 )

( 1 2 4 **5** **8** ) ( 1 2 4 **5** **8** )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one **whole** pass without **any** swap to know it is sorted.

**Third Pass:**

( **1** **2** 4 5 8 ) ( **1** **2** 4 5 8 )

( 1 **2** **4** 5 8 ) ( 1 **2** **4** 5 8 )

( 1 2 **4** **5** 8 ) ( 1 2 **4** **5** 8 )

( 1 2 4 **5** **8** ) ( 1 2 4 **5** **8** )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
static void Main(string[] args) { int[] intArray = {5,1,4,2,8}; bool sortFinished = false; while (!sortFinished) { sortFinished = true; for (int i = 0; i < intArray.Length; i++) { if (i < intArray.Length - 1 && intArray[i] > intArray[i + 1]) { sortFinished = false; int cache = intArray[i + 1]; intArray[i + 1] = intArray[i]; intArray[i] = cache; } } } foreach (int i in intArray) { Console.WriteLine(i.ToString()); } Console.ReadLine(); } |