Question

Sorting: (40 points) 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) Explain the time complexity of the above two operations. (10 points)

Answer 1

Insertion Sort Algorithm

Following are some of the important characteristics of Insertion Sort:
It is efficient for smaller data sets, but very inefficient for larger lists.
Insertion Sort is adaptive, that means it reduces its total number of steps if a partially sorted array is provided as input, making it efficient.
It is better than Selection Sort and Bubble Sort algorithms.
Its space complexity is less. Like bubble Sort, insertion sort also requires a single additional memory space.
It is a stable sorting technique, as it does not change the relative order of elements which are equal.
Insertion Sort Applications
The insertion sort is used when:
the array is has a small number of elements.
there are only a few elements left to be sorted.
Sorting short lists. If you know your lists are never going to contain more than say 25 elements, then insertion sort is an excellent choice. It is very simple and it’s going to be more efficient than any more complicated sort like quick-sort.
Sorting “almost sorted” lists. If you know that no element is more than say 25 locations from its final location in sorted order (the data could have been produced from another program) or that at most say 25 elements are out of order (the remaining elements are already in sorted order), then insertion sort is again an excellent choice. Again it is simple and essentially unbeatable on these kinds of lists.
Sorting Small Sub-lists in Quick-sort. When the current sub-list is small (say <= 25 elements), it is more efficient to use Insertion-sort on the sub-list than to continue recursing down to a base case of a 1 element list in quick-sort. This idea can also be used in merge-sort.

Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Merge Sort:

uses in database scenarios, because stable (multi-key sort) and external (results don’t all fit in memory). Useful in distributed scenarios where additional data arrive during or after sorting. Memory consumption prevents wider use on small devices.

Merge Sort is useful for sorting linked lists in O (n log n) time.

It is used in Inversion Count Problem.

We can use it in External Sorting.

If there is a lot of parallelization occurs, then the parallelizing Mergesort is more straightforward than other sort algorithms.

Quick Sort:

Applications: commercial application use quicksort

- genarally it runs fast
-no additional memory is required
life critical:-
1.medical monitoring
2.life support in aircraft & spacecraft)
-mission critical :-
1.monitring & control in industrial & reaserch plants handling dangerous material
2.control for aircraft.
3.defence
When there is a limitation on memory then randomised quicksort can be used. merge sort is not an in-place sorting algorithm and requires some extra space.