Bubble Sort

Download the code here: [wpdm_package id=’1310′]

Among the many sorting algorithms, you will come to see the bubble sort as the simplest algorithm, though the slowest. Let us first go through the algorithm for the same:

algorithm:

[sourcecode language=”c”]
bubbleSort(Array)
{
repeat
swapped = false
for i = 1 to length(Array) – 1 do:

if Array[i-1] > Array[i] then
/* swap them */
swap( Array[i-1], Array[i] )
swapped = true
end if
end for
until not swapped

}[/sourcecode]

Let us now see, given an array, how this works. Suppose the array is :

4 5 2 1 3

1st iteration:             2nd iteration:     3rd iteration:

4 5 2 1 3                  2 4 1 3 5             1 2 3 4 5

4 2 5 1 3                  2 1 4 3 5             1 2 3 4 5

4 2 1 5 3                  2 1 3 4 5

4 2 1 3 5

And then you get the sorted array which is 1 2 3 4 5.

Time complexity:

Worst case: O(n^2)

Best case: O(n)

Average case: O(n^2)

Space Complexity: O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *