Question

a. We studied several sorting algorithms. Every sorting algorithm has their own special reason where it can only use. Can you explain carefully in which situation the following algorithms would be best sorting algorithm to use in an application. (10 points) i. Insertion sort ii. Selection sort iii. Merge sort iv. Quick sort b. You are given a string of elements as below, Canopus, Mimosa, Betelgeuse, Deneb, Stars, Pollux, Antares, Sirius, Hader i. Your task is to insert the above elements into a binary max-heap which is initially empty. Circle the final tree after completing insertion and show the array representation. (10 points) ii. On the above max-heap tree, perform 2 remove operations. Show the final tree and the array representation. (10 points) iii. Explain the time complexity of the above two operations. (10 points)

Answer 1

(a) (i) Insertion Sort:

In case of the following scenarios, insertion sort is the best sorting algorithm:

(1) When the input array is almost sorted (only a few out of order elements).

(2) When the array size is small.

(ii) Selection Sort:

In case of the following scenarios, selection sort is the best sorting algorithm:

(1) When there are big number of records.

(2) Available memory space is limited.

(3) The given array is already sorted.

(iii) Merge Sort:

In case of the following scenarios, merge sort is the best sorting algorithm:

(1) When parallel threading or multi-programming support is required.

(2) When linked list sorting is required.

(3) When the given array is sorted in the reverse order.

(iv) Quick Sort:

In case of the following scenarios, quick sort is the best sorting algorithm:

(1) When array sorting is required.

(2) When fast (quick) sorting is required.

The given question has two questions included in it. As per the HOMEWORKLIB RULESs I have answered the first question and requesting you to re-post the remaining question as a separate one.
Please comment in case of any doubt.
Please upvote if this helps.