CS 2336
Bubble Sort
Vidroha debroy
Material adapted courtesy of Prof. Xiangnan Kong and Prof.
Carolina Ruiz at Worcester Polytechnic Institute
Searching for a number
Find a specific number 91 -
3
3
26
54 73
103 88 91
68
131
19
Searching for a number
Find a specific number 91 - what about now?
3 73
26 13
54 87 17 73
21 71 85
61 35 383 102
103 88 91
68 41
97 114 22
11 131
94 57
49 12 19
8 63
39 66 111
76
99
Why Sorting?
Practical Application
People by last name
Countries by population
Search engine results by relevance
Fundamental to other algorithms
Different algorithms have different asymtotic and constant-
factor trade-offs
no single best sort for all scenarios
knowing one way to sort just isn't enough
Keeping data in order allows it to be searched
more efficiently
Sorting
Sorting: Rearranging the values in an array or collection into a
specific order (usually into their "natural ordering").
one of the fundamental problems in computer science
it is estimated that 25~50% of all computing power is used for
sorting activities.
Popular Sorting algorithms:
bubble sort: swap adjacent pairs that are out of order
selection sort: look for the smallest element, move to front
insertion sort: build an increasingly large sorted front portion
merge sort: recursively divide the array in half and sort it
heap sort: place the values into a sorted tree structure
quick sort: recursively partition array based on a middle value
Sorting Example
Bubble Sort
Problem Definition
Sorting takes an unordered collection and makes
it an ordered one.
1 2 3 4 5 6
Input: 77 42 35 12 101 5
1 2 3 4 5 6
Output: 5 12 35 42 77 101
One Idea: Bubble
Water
3 3 3
2 2 3
1 2 2
1 1 1
Air
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
77 42 35 12 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42Swap
77 77
42 35 12 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35Swap35
77 77 12 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12Swap12
77 77 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 101 5
No need to swap
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 5 Swap101
101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
Bubble the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
The Bubble Up Algorithm
Bubble-Sort-step1( A ):
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp
Need More Iterations
Notice that only the largest value is correctly
placed
All other values are still out of order
So we need to repeat this process
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
Repeat Bubble Up How Many Times?
If we have N elements
And if each time we bubble an element, we place it in
its correct location
Then we repeat the bubble up process N 1 times.
This guarantees well correctly place all N elements.
Bubbling All the Elements
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
N-1
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
1 2 3 4 5 6
5 12 35 42 77 101
The Bubble Up Algorithm
Bubble-Sort( A ):
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
The Bubble Up Algorithm
Bubble-Sort( A ):
for i = 1 (N 1):
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
The Bubble Up Algorithm
Bubble-Sort( A ):
To do N-1 iterations
for i = 1 (N 1):
To bubble a value
Inner loop
Outer loop
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Reducing the Number of Comparisons
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
Reducing the Number of
Comparisons
Assume the array size N
On the ith iteration, we only need to
do N-i comparisons.
For example:
N=6
i = 4 (4th iteration)
Thus, we have 2 comparisons to do
1 2 3 4 5 6
12 35 5 42 77 101
The Bubble Up Algorithm
Bubble-Sort( A ):
for i = 1 (N 1):
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
The Bubble Up Algorithm
Bubble-Sort( A ):
for i = 1 (N 1):
for k = 1 (N i):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Code Demo
An Animated Example
N 8
i 1
k
98 23 45 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 1
98 23 45 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 1
Swap
98 23 45 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 1
Swap
23 98 45 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 2
23 98 45 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 2
Swap
23 98 45 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 2
Swap
23 45 98 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 3
23 45 98 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 3
Swap
23 45 98 14 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 3
Swap
23 45 14 98 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 4
23 45 14 98 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 4
Swap
23 45 14 98 6 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 4
Swap
23 45 14 6 98 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 5
23 45 14 6 98 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 5
Swap
23 45 14 6 98 67 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 5
Swap
23 45 14 6 67 98 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 6
23 45 14 6 67 98 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 6
Swap
23 45 14 6 67 98 33 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 6
Swap
23 45 14 6 67 33 98 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 7
23 45 14 6 67 33 98 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 7
Swap
23 45 14 6 67 33 98 42
1 2 3 4 5 6 7 8
An Animated Example
N 8
i 1
k 7
Swap
23 45 14 6 67 33 42 98
1 2 3 4 5 6 7 8
After First Pass of Outer Loop
N 8
i 1
k 8 Finished first Bubble Up
23 45 14 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 1
23 45 14 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 1
No Swap
23 45 14 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 2
23 45 14 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 2
Swap
23 45 14 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 2
Swap
23 14 45 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 3
23 14 45 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 3
Swap
23 14 45 6 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 3
Swap
23 14 6 45 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 4
23 14 6 45 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 4
No Swap
23 14 6 45 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 5
23 14 6 45 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 5
Swap
23 14 6 45 67 33 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 5
Swap
23 14 6 45 33 67 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 6
23 14 6 45 33 67 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 6
Swap
23 14 6 45 33 67 42 98
1 2 3 4 5 6 7 8
The Second Bubble Up
N 8
i 2
k 6
Swap
23 14 6 45 33 42 67 98
1 2 3 4 5 6 7 8
After Second Pass of Outer Loop
N 8
i 2
k 7 Finished second Bubble Up
23 14 6 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 1
23 14 6 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 1
Swap
23 14 6 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 1
Swap
14 23 6 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 2
14 23 6 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 2
Swap
14 23 6 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 2
Swap
14 6 23 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 3
14 6 23 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 3
No Swap
14 6 23 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 4
14 6 23 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 4
Swap
14 6 23 45 33 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 4
Swap
14 6 23 33 45 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 5
14 6 23 33 45 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 5
Swap
14 6 23 33 45 42 67 98
1 2 3 4 5 6 7 8
The Third Bubble Up
N 8
i 3
k 5
Swap
14 6 23 33 42 45 67 98
1 2 3 4 5 6 7 8
After Third Pass of Outer Loop
N 8
i 3
k 6 Finished third Bubble Up
14 6 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 1
14 6 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 1
Swap
14 6 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 1
Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 2
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 2
No Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 3
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 3
No Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 4
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fourth Bubble Up
N 8
i 4
k 4
No Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
After Fourth Pass of Outer Loop
N 8
i 4
k 5 Finished fourth Bubble Up
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fifth Bubble Up
N 8
i 5
k 1
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fifth Bubble Up
N 8
i 5
k 1
No Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fifth Bubble Up
N 8
i 5
k 2
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fifth Bubble Up
N 8
i 5
k 2
No Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fifth Bubble Up
N 8
i 5
k 3
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
The Fifth Bubble Up
N 8
i 5
k 3
No Swap
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
After Fifth Pass of Outer Loop
N 8
i 5
k 4 Finished fifth Bubble Up
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
N 8
i 5
k 4
6 14 23 33 42 45 67 98
1 2 3 4 5 6 7 8
Analysis of Bubble Sort and Loop
Invariant
Bubble Sort Algorithm
Bubble-Sort( A ):
To do N-1 iterations
for i = 1 (N 1):
To bubble a value
Inner loop
Outer loop
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
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):
To bubble a value
Inner loop
Outer loop
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
Loop Invariant for Bubble Sort
To do N-1 iterations
for i = 1 (N 1):
To bubble a value
Inner loop
Outer loop
for k = 1 (N 1):
if A[k] > A[k+1]:
Swap( A, k, k+1 )
By the end of iteration i the right-most i
items (largest) are sorted and in place
N-1 Iterations
1 2 3 4 5 6
42 35 12 77 5 101 1st
1 2 3 4 5 6
35 12 42 5 77 101 2nd
1 2 3 4 5 6
N-1
12 35 5 42 77 101 3rd
1 2 3 4 5 6
12 5 35 42 77 101 4th
1 2 3 4 5 6
5 12 35 42 77 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
Bubble Sort Time Complexity
Best-Case Time Complexity
The scenario under which the algorithm will
do the least amount of work (finish the
fastest)
What if we had a pass and nothing was
swapped? What does that tell us?
Worst-Case Time Complexity
The scenario under which the algorithm will
do the largest amount of work (finish the
slowest)
Summary
Bubble Up algorithm will move largest value to its correct location
(to the right)
Repeat Bubble Up until all elements are correctly placed:
Maximum of N-1 times
Can finish early if no swapping occurs
We reduce the number of elements we compare each time one is
correctly placed
Not the most efficient algorithm around but is easy to understand
