Search code examples
algorithmsortingbubble-sort

Bubble sort performance

If bubble sort takes 200 sec to sort 200 names then how many items it can sort in 800 secs?

Calculating number of comparisons can give us the solution. How can we calculate the number of comparisons it takes to sort 200 names ? Do we have to consider the best case ?

Solution
    1. Bubble sort is O(n2). Do your maths. Big O just gives an idea of relative time, you can guess rough estimate of time. Not exact.
    2. BubbleSort takes n-1 comparisons in first go, n-2 in second, and so on. So you have total (n-1) + (n-2) + .. +1. Do some maths again?
    3. Bubble Sort is so pathetic that there is no best case![1]

    (obviously you can write a smart bubble sort that does not sort an already sorted array)

    BUBBLESORT A
 for i = 1 to A.length 1
  for j = A.length downto i+1
    if A[j]  < A[j - 1]
     exchange A[j] with A[j-1]

    from The Introduction to Algorithms - CLRS

    [1] On #3. See http://en.wikipedia.org/wiki/Bubble_sort it mentions an optimized inner loop that identified the sorted remaining array and makes a best case O(n) -- sorry about that.