-1

I gave a written round of a company. I have a doubt in a question can anyone help me?

which is the fastest sorting algorithm among the following?
a - bubble sort
b - shell sort
c - heap sort
d - quick sort

I'm confused b/w quick sort and heap sort both have a time complexity of O(nlogn).

svick
  • 236,525
  • 50
  • 385
  • 514
akash
  • 1,801
  • 7
  • 24
  • 42
  • 3
    That's a really badly phrased question. The answer depends on what exactly does “fast” mean and it could also depend on the data. – svick Jul 29 '12 at 19:49
  • fast means i think in terms of time complexity for a larger n – akash Jul 29 '12 at 19:52
  • That was never specified. For smaller N, it could be more efficient in terms of space and time to use bubblesort. – Makoto Jul 29 '12 at 19:54
  • @akash But that's not clear from the question at all. And asymptotic time complexity is still not specific enough: it could mean average case complexity or worst case complexity. – svick Jul 29 '12 at 19:55
  • possible duplicate of [When is each sorting algorithm used?](http://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used), as well as [quicksort-vs-heapsort?](http://stackoverflow.com/questions/2467751/quicksort-vs-heapsort?lq=1) – nawfal Jun 16 '14 at 07:27

3 Answers3

10

There's no "fastest" sorting algorithm.

Theoretical performance of an algorithm always depends on the input data. In their respective worst cases, Heap sort is faster than Quick sort. In average case, Quick sort is faster. It is probably possible to concoct a custom-tailored best case for each algorithm to make it outperform all the others.

That is actually the reason such "hybrid" algorithms as Introsort exist: Introsort begins with Quick sort and switches to Heap sort if it sees that Quick sort is struggling with this specific input.

On top of that the real-life performance of any algorithm can be significantly affected by how well it works on a specific hardware platform. A theoretically "fast" algorithm can lose miserably to a primitive and "slow" one, if the latter is in better "sync" with the properties of the hardware.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • Exactly, the question would be hard to answer even if it was specified properly, which it isn't. – svick Jul 29 '12 at 19:57
4

See Wikipedia: Heapsort

Heapsort: Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime

Stefan Profanter
  • 6,458
  • 6
  • 41
  • 73
2

In the average case: Quick-Sort, since the constant of its O(nlgn) running time is better.

In the worst case: Heap-Sort, since in the worst case, the running time of Quick-Sort is O(n2).

Avi Cohen
  • 3,102
  • 2
  • 25
  • 26