What are the major steps in Divide and Conquer? Use quicksort to illustrate the steps. Also give the time complexities of the major steps, assuming sorting n elements. Divide: partition the array using a pivot. Theta(n). Conquer: sort the portion to the left of the pivot recursively, sort the portion to the right of the pivot recursively. Combine: nothing. O(1). Suppose you are required to sort a very long sequence of numbers. Assume that worst-case time complexity is the only measurement. Also, we do not have any prior knowledge of the input sequence. Between quicksort and heapsort, which is the better algorithm for this problem? Why? Heapsort requires Theta(n log n) time. Quicksort requires Theta(n^2) time. Therefore heapsort is the better algorithm. Grading: for the answer; for the reason. Suppose you are required to sort a very long sequence of numbers. Assume that worst-case time complexity is the only measurement. Suppose that we know that the inversion number of the input sequence is Theta(n^1.1), where n is the length of the input sequence. Between insertion sort and heapsort, which is the better algorithm for this problem? Why? Heapsort requires Theta(n log n) time. Insertion sort requires Theta(n^1.1) time. Therefore heapsort sort is the better algorithm. Grading: for the answer; for the reason.
A divide and conquer algorithm consists of 3 steps:
1) Dividing the problem into sub-problems.
2) Solving the sub-problems recursively.
3) Combine the solutions.
In quick sort:
a) We select a pivot, which is selected randomly. Now we iterate the array once to divide the array in to two parts. The left part has all the elements less than pivot and the right part has all the elements greater than pivot.
b) We sort the left and right parts using the same method. We again select a pivot and divide the left and right parts and it happens until we reach an array of size 1. Where it is already sorted.
c) We just concatenate the left array, pivot and right array. By the time we are doing this, the left and right array are already sorted. The final result after the concatenation is sorted.
Homework Sourse
