Bubble Sort

Bubble Sort
Pseudocode and Flowchart

BubbleSort( int a[], int n)

Begin
 for i = 1 to n-1
  sorted = true
       for j = 0 to n-1-i
                 if a[j] > a[j+1]
                 temp = a[j]
                 a[j] = a[j+1]
                 a[j+1] = temp
           sorted = false
        end for
       if sorted
         break from i loop
 end for
End


Bubble sort uses a loop (inside j loop) to travel thru’ an array comparing adjacent
values as it moves along. If an array element a[j] is greater than the element
immediately to its right a[j+1], it swaps them. The first time around, this process will
move or bubble the largest value to the end of the array. So for instance

5 3 1 9 8 2 4 7
will end up as
3 1 5 8 2 4 7 9


This process is repeated, on the second iteration, the second largest value will be
moved to the second last array position and so on.

In all, the bubble process (inside j loop) is repeated n-1 times for an array of size n.

Note for array of size 8, outside i loop repeats 7 times.
Complexity
Clearly for an array of size n, the outside loop repeats n-1 times.

To begin with the inside loop does n-1 comparisons, next time n-2 and so on. Finally
on the last iteration of the outside loop, the inside loop does 1 comparison. So on
average the inside loop does ((n-1) + 1) / 2 ≈ n/2 comparisons.

Therefore, the overall number of computation steps is n * n/2 = n2/2

Complexity of bubble sort = O(n2)