# 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)