Transcript Bubble Sort

Analysis of Bubble Sort and
Loop Invariant
N-1
N-1 Iteration
1
42
2
35
3
12
4
77
5
5
6
101
1
35
2
12
3
42
4
5
5
77
6
101
1
12
2
35
3
5
4
42
5
77
6
101
1
12
2
5
3
35
4
42
5
77
6
101
1
5
2
12
3
35
4
42
5
77
6
101
Bubble Sort Algorithm
Bubble-Sort( A ):
To do N-1 iterations
for i = 1 … (N – 1):
Python Code in http://www.geekviewpoint.com/python/sorting/bubblesort
Outer loop
for k = 1 … (N – 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Inner loop
To bubble a value
Bubble Sort Time Complexity
• Best-Case Time Complexity
– The scenario under which the algorithm will do
the least amount of work (finish the fastest)
• Worst-Case Time Complexity
– The scenario under which the algorithm will do
the largest amount of work (finish the slowest)
Bubble Sort Time Complexity
Called Linear Time
O(N2)
Order-of-N-square
• Best-Case Time Complexity
– Array is already sorted
– (N-1) + (N-2) + (N-3) + …. + (1) = (N-1)* N / 2
comparisons
Called Quadratic Time
O(N2)
Order-of-N-square
• Worst-Case Time Complexity
– Need N-1 iterations
– (N-1) + (N-2) + (N-3) + …. + (1) = (N-1)* N / 2
Loop Invariant
• It is a condition or property that is guaranteed to be correct with
each iteration in the loop
• Usually used to prove the correctness of the algorithm
To do N-1 iterations
for i = 1 … (N – 1):
Outer loop
for k = 1 … (N – 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Inner loop
To bubble a value
Loop Invariant for Bubble Sort
To do N-1 iterations
for i = 1 … (N – 1):
• By the end of iteration i  the right-most i items
(largest) are sorted and in place
Outer loop
for k = 1 … (N – 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Inner loop
To bubble a value
N-1
N-1 Iterations
1
42
2
35
3
12
4
77
5
5
6
101
1st
1
35
2
12
3
42
4
5
5
77
6
101
2nd
1
12
2
35
3
5
4
42
5
77
6
101
3rd
1
12
2
5
3
35
4
42
5
77
6
101
4th
1
5
2
12
3
35
4
42
5
77
6
101
5th
Correctness of Bubble Sort (using
Loop Invariant)
• Bubble sort has N-1 Iterations
• Invariant: By the end of iteration i  the right-most i
items (largest) are sorted and in place
• Then: After the N-1 iterations  The right-most N-1
items are sorted
– This implies that all the N items are sorted