-2

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?

closed as too broad by user40980, user22815, durron597, Ixrec, gnat Sep 16 '15 at 13:44

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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.

  • 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
2

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.
0

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²)

0

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.

-1

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.

-1

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.

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