Self doubt

Question

You are asked to sort 15 randomly generated numbers. One should prefer—

(a) Bubble sort (b) Quick sort (c) Merge sort (d) Heap sort

I think the answer should be c or d

crct me???

Comments

I think B. Because for Merge sort we required create two dynamic array.
More ever this is given in cormen.
"The quicksort algorithm has a worst-case running time of ‚.n 2 / on an input array
of n numbers. Despite this slow worst-case running time, quicksort is often the best
practical choice for sorting because it is remarkably efficient on the average: its
expected running time is ‚.n lg n/, and the constant factors hidden in the ‚.n lg n/
notation are quite small. It also has the advantage of sorting in place (see page 17),
and it works well even in virtual-memory environments."

---

But quicksort has worst-case time complexity as O(n^2) instead Merge-sort and Heap-sort have O(nlogn), then why B).

---

shubhanshu if you go for worst case...then quick sort is not good...because of its O(n^2) complexity....but for the best case..quick sort  works faster...in comparison to merge and heap sort..check slide 27

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

http://warp.povusers.org/SortComparison/

but such questions will not be asked because it creates confusion //if asked then they will mention the various cases like..best or worst

---

(b) Quick sort ..

 

1. https://gateoverflow.in/55178/You-are-asked-sort-randomly-generated-numbers-should-prefer 

 

2. https://gateoverflow.in/16934/Randomly-generated-numbers-should-prefer-which-sorting-quick 

 

3. https://gateoverflow.in/221092/Sorting 

 

4. https://gateoverflow.in/115663/Question

 

Answer 1

Answer is Quick Sort. (That is why it's name is Quick I guess :D )
The worst case time complexity is O(n square) but worst case is very less likely to happen.
So in most of the cases it is going to take O(nlogn)..
Now mergesort also takes O(nlogn).... but  the actual time taken for quicksort is less than merge & heapsort. ( The constant for quicksort is less than mergesort).

 In a program, I took 5 lakh random elements in the range 0-100   , it took more time than mergesort.
But I modified it & took 5 lakh elements in the range 0-5lakh .. i.e randomness was more & less repeated elements.
It took almost equal or less than mergesort.

Prefer bubble or insertion sort only when they are nearly sorted. (Do not prefer quicksort, quicksort will take huge time, worst case happens in quicksort when they are already or reversely sorted)

Answer 2

I think answer should be Quick Sort or Bubble sort as number of elements to be sorted are only15..better use Quick Sort or bubble sort as there constant factor is less compared to Merge Sort and Heapsort. For sorting large number of elements Complexity becomes relevant but for small number of elements..look for sorting that has small constant value.

Answer 3

I think we should apply any of the sorting algorithm as it have only 15 elements and it can be done in O(1) time.

So for constant length input the sorting algorithm  does not matter.