Wednesday, November 25, 2009

Art of computer programming -Sorting #4

Bubble sort
Bubble sort is the most well known sort. The idea of bubble sort is very straight forward. We compare adjacent elements and rearrange them. So element 1 and element 2 are compared and if element 1 is > element 2 then they are swapped, next element 2 and element 3 are compared and so on. In the first pass the largest element will be swapped to position n-1. In the second pass second largest element will reach n-2 etc. So in the nth pass ith largest element will reach n-i. There are a total of n passes. Now there are very little interesting things about this sort.

Point to note
The algorithm is inefficient for small and large lists. For small lists insertion sort maybe used and O(n^2) sorting is not recommended for large lists.
Knuth says that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems"
Bubble sort is 40% slower than selection sort and 5 times slower than insertion sort.

procedure bubbleSort( A : list of sortable items ) defined as:
swapped := false
for each i in 0 to length(A) - 2 inclusive do:
if A[i] > A[i+1] then
swap( A[i], A[i+1] )
swapped := true
end if
end for
while swapped
end procedure

Worst case performance : O(n^2)
Best case performance : O(n)
Average case performance : O(n^2)
Worst case space complexity: O(1)

Thanking you,