Definition:
Bubble sort is another type of sorting algorithm that sort unsorted lists and arrays.
In worst and average case its time complexity is O(n^2) (n square). However, In best case, time complexity of this algorithm is O (n).
Properties of Bubble Sort:
- Stable,
- Adaptive,
- O(n^2) comparison and swap,
- O(1) memory space.
Its properties are mostly same as insertion sort.
How does it work?
In bubble sort,
1. It starts at the beginning of unsorted list and it compares every adjacent pair.
2. If the elements in the pair are not right position, swap them.
3. The largest (or smallest ) one goes to the at the end of the list.
4. This iteration goes on until list is getting sort.
Elements in the list move like bubbles in the water. They move upward to reach surface of the water.
In the figure below, you can see the animated bubble sort example.
Animated Bubble Sort Example
Another example for bubble sort:
Bubble Sort Example
Animation:
For better understanding, go to this animation page.
Pseudocode:
for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end
References:
Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.
Programming Pearls by Jon Bentley. Addison Wesley, 1986.
http://www.sorting-algorithms.com/
Figure from: http://en.wikipedia.org
For more algorithms, go to Algorithms Section.
