Question

2. Sometimes you want to sort lots of data, but you only need the smallest (or largest) K items instead of all items. For example, maybe you want to give awards to the ten students with the best GPAs. If you have thousands of students, you could waste time sorting all of them just to find the top ten. Perhaps we can adapt an existing sorting algorithm so that it works faster if we just want to find and sort the smallest (or largest) K items Suppose we can start with either insertion sort or selection sort. Part A: Which one is easier to modify so that it efficiently gives us only the smallest K items (in sorted order) instead of all items? Part B: Describe the changes needed to make this happen. Part C: Briefly explain why the other algorithm cannot be modified to do what we want efficiently

Answer 1

Answer)

The selection sort is an advantage over the insertion sort as the number of writes is in O(n) whereas the insertion sort is in O (n^2).

The insertion sort performs less comparison than the selection sort which depends on the degree of sortness of the mentioned array. During the selection sort one must scan the left out part of the array while placing an element. Insertion refers to scanning as many elements are needed which means that when an array is sorted almost or already then the insertion sort performs in O (n) times.

Usually, insertion sort will perform less comparisons than selection sort, depending on the degree of "sortedness" of the array. While selection sort must scan the remaining parts of the array when placing an element, insertion sort only scans as many elements as necessary. That means that when the array is already sorted or almost sorted, insertion sort performs in O(n) time.

The other algorithms will not help as Selection Sort has a way to always performs in quadratic time and also selection sort is always a better alternative when one uses an array, while an insertion sort might perform better when one uses a linked list.

Hope this answer helps. :) Happy to help.