Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'v been working on sorting for a while now but I can't figure these two questions apart, I'm kind of getting mixed up somewhere ... Somebody help

a) Which sorting algorithms have a different worst case complexity than their average case?

b) Which sorting algorithms have a different best case complexity than their average case?

share|improve this question
1  
Please mark your homework with the [homework] tag. It's poor form to ask us to do your homework for you. –  S.Lott May 20 '11 at 10:06

4 Answers 4

The most obvious example would be Quicksort -- its average case is O(N log N), and worst case is O(N2). As its normally written, the best case is O(N log N), but some versions have included a pre-scan to exit early when data was sorted, which gives a best-base of O(N), though I suppose it's open to argument that it's no longer purely a Quicksort at that point.

I don't know whether it does any more, but the implementation of qsort in Microsoft's C standard library used to do that -- mostly to make up for a poor implementation (always used the first element as the pivot) that would otherwise have been O(N2) for sorted data.

share|improve this answer
2  
I disagree with best case O(N) –  user281377 May 20 '11 at 7:02
1  
@ammoQ: agree. After Quicksort finishes one pass (partitioning) on the data, it will always have to call Quicksort recursively on the two partitions, because during the first pass it has no way of knowing that the data is already sorted inside each partition. –  rwong May 20 '11 at 7:26
2  
@ammoQ: Could you explain that? Making a single pass over the input array to check if it is already sorted, sounds like best case O(N) to me. –  nikie May 20 '11 at 8:58
    
nikie: but that check isn't part of quicksort! What happens instead is the same recursive partitioning as for an unsorted array; in fact, depending on the implementation, an already sorted array might be a worst case. –  user281377 May 22 '11 at 18:26

Here's a complete overview of the complexities.

Some of the most popular ones:

  • Quick sort: O(n²) in the worst case, O(n lg(n)) on average and in the best case.
  • Insertion sort: O(n²) in the worst case & average case, O(n) in the best case.
share|improve this answer
    
Love the bogosort. :-D –  Denis de Bernardy May 20 '11 at 10:25

Insertion sort is an example of a sort algorithm with a better best case than average case. Best case is O(n), average case and worst case are O(n²)

share|improve this answer

The crucial thing here is recognizing that the algorithm needs to take shortcuts to avoid having to compare each element to every other element (which would result in a O(N^2) algorithm) but only to some of the other elements and to do it again when sorting those elements. This is the reason why "divide work in piles and handle each of those piles by dividing it in piles and handle each of those piles etc" ends up with O(N log N) complexity.

The hard part is picking those elements, and to handle working with those elements. Picking is hard because you must choose well to get the subpiles equally sized. Managing is hard because you cannot spend too much time moving things around if you want a fast algorithm.

For instance, QuickSort works by choosing an element (traditionally called "pivot") and divide the work in two piles. One having elements smaller than the pivot, and the other having larger. Then quicksort each pile, and merge the two sorted piles back. If the pivot is the smallest element each time, you end up with an empty sub-pile and a big subpile with all the elements but the pivot. This will result in a worst case of O(N^2). If you choose well, you get half-sized sub-piles and a running time of O(N log N).

So a typical way to choose the pivot is to look at three randomly chosen values from the pile and choose the one in the middle. This at least avoids the empty sub-pile.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.