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 reasonable quickly in all cases. There is barely enough memory to hold the 45,000 record. (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 the completed quickly in every single case.

Explanation / Answer

(a)

Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios. Heap sort algorithm is divided into two basic parts. Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal.

(b)

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst case complexity are of (n2), where n is the number of items.

(c)

Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being (n log n), it is one of the most respected algorithms. Merge sort first divides the array into equal halves and then combines them in a sorted manner.

(d)

Insertion sort This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of (n2), where n is the number of items.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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