Please choose the best suitable algorithm from the list to solve each of the fol
ID: 3840175 • Letter: P
Question
Please choose the best suitable algorithm from the list to solve each of the following problems.
Insertion sort algorithm
Selection sort algorithm
Merge-Sort algorithm
Heap-Sort algorithm
Quick-Sort algorithm
Counting-Sort algorithm
Radix-Sort algorithm
Bucket-Sort algorithm
None of the Above
(5) Suppose you are running a library catalog. You know that the books are almost in sorted ascending order by title, except for few books which are in the wrong place. To sort the catalog, what sorting algorithm would work best for this case?
(5) Suppose you are working on an ATM device that has only 8KB (8,192 bytes) of free memory, and you want to sort the 2,000,000-transaction history by the amount of money discarding the original order of transactions. To sort the transactions, what sorting algorithm would work best for this case?
(5) Suppose you want to determine which of your Facebook friends are early adopters, and you decide to sort them by their Facebook account ids, which are 64-bit integers. (Recall that you are super popular, so you have very many Facebook friends.) To sort the account ids, what sorting algorithm would work best for this case?
(5) Suppose you are working on a legacy system of XYZ Inc. which maintains multiple customer account lists. The lists are already sorted in ascending order by account numbers and all account numbers are unique. Since maintaining multiple lists can be error-prone and slowed down the operation, you decide to merge all lists into one sorted list by account numbers. What algorithm would work best for this case?
Explanation / Answer
Insertion sort algorithm: Since the list is already sorted and a few books may be out of place. Insertion sort takes each unsorted element and puts the element in its rightful place by making the necessary adjustments prior to the sorted list. The average and worst case in O(n2) so as a result this algorithm is not recommended for large n but suits for the present condition for library scenario. Heap sort algorithm: Heap sort suits the requirements to carry sorting of 2,000,000-transaction history with limited space of 8KB (8,192 bytes) as it operates with O(n*log(n)) and O(1) time and space complexities. Only O(1) additional space is required since the heap is built inside the array to be sorted, so considering the space limitations we have Heap sort would be the best alternative. Radix Sort algorithm: Since it is the sorting algorithm used for sorting elements from the least significant bit to the most significant bit, this very condition suits for its implementation here. The number of passes required would be the size of each element which is 64 since we are sorting 64 bit integers (account ids). This algorithm will run in time O(kn), for you k=64 and n=number of account ids. Merge sort: Since the two lists are already in sorted order, so we use Merge sort, which is used for creating 2 sorted lists and then merging both by checking each respective items from the two sorted lists, the smaller one out of the two makes to the final list. This operated with time complexity of O(nlog n).