Question

1. Write MaxheapPriorityQueue constructor, which takes an array of data, and construct the max

   heap priority queue using bottom-up algorithm. Assuming bubbleDown method is provided.

2. What is the best-case and worst-case of insertionSort?

3. What is the best-case and worst-case of mergeSort?

4. What is the best-case and worst-case of quickSort?

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

INSERTION SORT

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n²)).

MERGE SORT

In the best case, the input is already sorted (i.e., is one run), so the natural merge sort need only make one pass through the data. In many practical cases, long natural runs are present, and for that reason natural merge sort is exploited as the key component of Timsort. T=O(n*log(n))

In the worst case, the number of comparisons merge sort makes is given by the sorting numbers. These numbers are equal to or slightly smaller than (n ⌈lg n⌉ − 2^{⌈lg n⌉} + 1), which is between (n lg n − n + 1) and (n lg n + n + O(lg n))

QUICK SORT

The worst case of quick sort is O(n²) for already sorted input, if the pivot was chosen as the first or the last element. With the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e. O(n log(n)).

Note: Brother according to HomeworkLib's policy we are only allowed to answer 3 partS if there are many. So, I request you to post other part as separate posts.

Kindly revert for any queries

Thanks.