The standard Partition method in QuickSort uses the first element in the (sub) array as a pivot
Question:
The standard Partition method in QuickSort uses the first element in the (sub) array as a pivot element, which is used to split the array into left (smaller elements) and right(larger elements) The choice of pivot affects the runtime of the algorithm.
a) Write the QuickSort method/function/procedure.
public static void QuickSort (int|] A, int first, int last) {
}
b) What is the worst case runtime for the standard QuickSort algorithm? What kind of data causes the worst case?
c) What is the average case runtime for the standard QuickSort algorithm? What kind of data gives the average case?
d) Identify and discuss TWO of the methods that can be used to "fix" the "worst case" runtime.
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest