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.

Algorithm

Thanking you,

procedurebubbleSort( A:list of sortable items )defined as:

do

swapped := false

for eachiin0tolength(A) - 2inclusive do:

ifA[i] > A[i+1]then

swap( A[i], A[i+1] )

swapped := true

end if

end for

whileswappedend procedure

Worst case performance : O(n^2)

Best case performance : O(n)

Average case performance : O(n^2)

Worst case space complexity: O(1)

Layman

i don love bubble sort . i love quick sort combined with insertion sort for the best performance . if i try to use it for tree then ofcourse heap sort

ReplyDeleteOf course.....but there is something called bubble sort that exists...and hence it has to be discussed. Other sorts are also discussed in other posts

ReplyDelete