Question

To sort  n randomly generated numbers. One should prefer which sorting algo ,Quick  or Heap?

Answer 1

Quick sort performs very gud if the elements are randomly generated.  even if Quick Sort and Merge Sort have same complexity on average and in best case scenario, the constants (hidden by the big-O notation) are much smaller in Quick Sort leading to a smaller running time on average.  looking at the table we can easy know that the comparision is between mege and quick . heap is not so efficient to be compared,(http://ddeville.me/2010/10/sorting-algorithms-comparison/)

Comments

Yes. I guess the point of the question is to show that with random generation, worst case of quick sort is extremely unlikely to happen.

Answer 2

I feel heap sort is preferable as at any moment if we wish to add any randomly generated element to the list then the list needs to be sorted after it to get the element in sorted order. so we can just add the element and call maxheapify or minheapify as our requirement  and get it sorted for the randomly added element

I feel if our list is static i.e data need not be added later then we can go ahead with sorting as the sorted order wont be affected later

but if we want to make any changes either add or delete any element then i feel heap is the best as it does minimal work for moving element and even maintaining the property

Answer 3

I think we can go for heap sort in this case as its complexity is nlogn for both worst and best case scenario.

Given that numbers are randomly generated quick sort may achieve its worst case of n^2  i.e. when most of the numbers are already sorted.

But on other side heap sort is not going to be hampered by already sorted numbers and going to give nlogn each time which is also the best case complexity of quick sort.