CODEWITHSUNDEEP
algorithmsortingbubble-sort
Rebooting
Rebooting

Reputation: 2938

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 ?

Upvotes: 0

Views: 4716

Answers (2)

Jim Balter
Jim Balter

Reputation: 16406

800 is 4 x 200. Bubble sort is O(n*n), so on average you can sort twice as many items in 4 times the time, so the expectation is 400 names, on average, if 200 was an average case.

Upvotes: 1

Nishant
Nishant

Reputation: 55856

  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.

Upvotes: 1

Related Questions