This homework covers the Sorting algorithms

1. Given the following situations, compute the runtime for each case:

a.Given 1000 data in decreasing order (i.e. given largest to smallest values) and you are using Merge Sort to sort them, what will be the exact runtime.

b.Given 500 random data and you are using Selection Sort, what will be the runtime?

c. Given 100 data in increasing order (smallest to largest) and you are trying to sort them using Insertion Sort, what will be the runtime.

d. Given 200 data in increasing order and you are trying to sort them using Quick Sort, what will be the runtime.

e. Given 1000 data in decreasing order, which algorithm will be the best one to use and what will be the corresponding runtime?

2.Implement Quick Sort using Lomuto Partition algorithm in C++. Make sure to give the source code along with results.

The pseudocode for Lomuto partition is given in the power point notes.

Make sure to call this partition from Quick sort function and main calls the Quicksort function by sending N number of data (N is user input)

Run the program and attach the results

3. Implement Bubble sort algorithm in C++. The pseudocode for Bubble sort is given as below:

BubbleSort (A, N)

for passNo 1 to (N-1)

for j 0 to (N-1-passNo)

if A[j] > A[j+1]

swap A[j] with A[j+1]

Call this function from main, and run with at least 10 data.

4. Given the following data: 23, 12, 1, 17, 0, 20

Illustrate Bubble sort using the above data. Show the detailed steps for pass 1.

5. Given the following Maxheap

50, 40, 30, 24, 15, 28, 20, 16, 19

Illustrate Heapsort using these data. Compute the runtime as well.