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)

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)