Among Selection Sort. Insert inn Sort, Merge sort, Quicksort, and Heap sort whic

Question

Among Selection Sort. Insert inn Sort, Merge sort, Quicksort, and Heap sort which algorithm would you choose in each list-sorting situation below? Justify your answers. The list has several hundred records. The records are quite long, but the keys are very short. The list has about 45,000 records. It is necessary that the sort be completed reasonably quickly in all cases. There is barely enough memory to hold the 45,000 records. The list has about 45,000 records, but it starts off only slightly out of order. The list has about 25.000 records. It is desirable to complete the sort as quickly as possible on the average, but it is not critical that the sort be completed quickly in every single case.

Explanation / Answer

(a)Merge Sort
Reason: Since recors are quite long and keys are very short, merge sort is preferred over others.

(b) Heap Sort
Reason: Since sorting has to be reasonably quick in this case heap sort complexity is nlog(n). Also we don't have extra memory so heap sort have advantage of in-place sorting.

(c) Insertion Sort
Reason: This sorting algorithm is best for this case because this method makes the least number of comparisons.

(d) Quick Sort
Reason: Average running time of quick sort is O(nlogn) on average and in worst cases it is O(n^2). So this is suitable for sorting quickly on average but not for every single case.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.