Among Selection sort, Insertion Sort, Mergesort, Quicksort, and Heapsort, which

Question

Among Selection sort, Insertion Sort, Mergesort, 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. The list has several hundred records. The records are quite long, but the keys are very short.
-Selection Sort or Insertion sort.Because the data to be sorted is small enough to fit into a processors main memory and can be randomly accessed i.e. no extra space is required to sort the records (Internal Sorting).

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.
-Heap sort. It is best when you don't need a stable sort and you care more about worst case performance than average case performance. It's guaranteed to be O(N log N), and uses O(1) auxiliary space, meaning that you won't unexpectedly run out of heap or stack space on very large inputs.

C. The list has about 45,000 records, but it starts off only slightly out of order.
- As list is large so merge sort is better than insertion sort in this case.if you implement the natural version you get a best case of O(N) with a typical and worst case of O(N log N).

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.
-Quick sort. It is best when you don't need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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