Foundation of algorithm Among Selection Sort, Insertion Sort, Quicksort, and Hea

Question

Foundation of algorithm

Among Selection Sort, Insertion Sort, Quicksort, and Heapsort, which algorithm would you choose in each list-sorting situation below? Justify your answers. (a) The list has several hundred records. The records are quite long, but the keys are very short. (b) 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. (c) The list has about 45,000 records, but it starts off only slightly out of order. (d) 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: MergeSort : As the records length is too long so we will use MergeSort as the complexity of this algorithm is O(log n).

B: HeapSort : As there is memory constraint, we will heapsort.

C: InsertionSort : This will use Insertion Sort as for the rest of the list which is in order, it would perform in O(n).

D: QuickSort : We will use QuickSort as the average time complexity for quicksort is O(nlogn) and the worst time complexity is O(n*n).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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