Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

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

closed as too broad by MichaelT, Snowman, durron597, Ixrec, gnat Sep 16 at 13:44

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

7 Answers 7

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
I disagree with best case O(N) –  user281377 May 20 '11 at 7:02
@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
@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

Bubble Sort, O(N) in the best case, O(N ** 2) in the average and worst cases.

To get the O(N) behaviour, set a swapped boolean to false at the beginning of each pass, set it to true whenever you swap two elements. If you have swapped elements, you need to do another pass. This also works as a general termination criterion, as long as comparisons are deterministic, which means you can skip an O(N) counting pass before starting.

share|improve this answer

There are implementations that first check if the array starts or ends with a sequence of elements in ascending or descending order, and takes advantage if many such elements are found. So best case is linear (if the array is mostly sorted in ascending or descending order). What the average case would be can be highly debatable.

share|improve this answer

Quick sort has complexity of:

  • O(n lg n) in the average case
  • O(n2) in the worst case

Quicksort: Average Case(which is difficult to understand) partition generates splits (0:n-1, 1:n-2, 2:n-3, … , n-2:1, n-1:0) each with probability 1/n.

If T(n) is the expected running time,then

T(n)=1/n ∑([T(k)+T(n-k-1)])+θ(n)

where k is going from 0 to n-1.

On solving,
∑k log k ≤ 1/2(sq(n)lg n-n log n)-1/8 sq(n)+n/4,
where k is going from 0 to n-1.
which comes out to be O(n2)

share|improve this answer
This answer is largely a duplicate (with a bit more greek) of the currently top voted answer posted in '11. –  MichaelT Oct 4 at 20:51

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