This is a problem about Quicksort Algorithm

The Quicksort algorithmhas a (n^2) worst case complexity even though it is only (n logn) on average. Our goal here is to observe the impact of this behavior difference in practice. We will also explore the space complexity of Quicksort. You must submit your program as part of your homework.

1. Write two versions of the Pivot procedure for the Quicksort algorithm: one version

public void int Pivot1st(Comparable[] a, int l, int r) { /* ...*/ }

that takes the first element a[l] of the input array as pivot, and one version

public void int PivotMid(Comparable[] a, int l, int r) { /* ...*/ }

that takes the middle element a[(l + r)/2] as pivot.

Each version should return the index p on array a[] where the pivot element lies after the pivoting process is finished, so that the following set of methods becomes complete and correct (i.e. a call to either Quicksort1st(a) or QuicksortMid(a) sorts the input array):

public void Quicksort1st(Comparable[] a, int l, int r) { if (r > l) { int p = Pivot1st(a, l, r); Quicksort1st(a, l, p 1); Quicksort1st(a, p + 1, r); } }

public void Quicksort1st(Comparable[] a) { Quicksort1st(a, 0, a.length 1); } public void QuicksortMid(Comparable[] a, int l, int r) { if (r > l) { int p = PivotMid(a, l, r); QuicksortMid(a, l, p 1); QuicksortMid(a, p + 1, r); } }

public void QuicksortMid(Comparable[] a) { QuicksortMid(a, 0, a.length 1); }

2. Write a program that: a) creates two copies a1st[] and amid[] of a random array of n integers (where n is a program input), b) sorts them by invoking respectively the Quicksort1st and QuicksortMid methods above, c) outputs the time needed for each of these two calls, d) then calls the same methods again on the sorted arrays, e) outputs the time needed for each of these two calls.

3.Execute your programs for successive powers of 10: n = 10,000, n = 100,000, n = 1,000,000, n = 10,000,000. Show the results on a comparative table. What are the execution times in each case, and what is the largest value of n that can be used from this list for each program? (NB: be prepared to handle stack overflows).

4.Modify your program to use this version of Quicksort where the first recursive call always handles the shorter segment of the partitioned array first, and the second recursive call is replaced by a simple iteration, then repeat the above test (NB: xxx stand for either 1st or Mid as before):

public void SafeQuicksortxxx(Comparable[] a, int l, int r) { while (r > l) { int p = Pivotxxx(a, l, r); if (p - l <= r - p) { SafeQuicksortxxx(a, l, p 1); // shorter part l = p + 1; // emulate SafeQuicksortxxx(a, p + 1, r) } else { SafeQuicksortxxx(a, p + 1, r); // shorter part r = p 1; // emulate SafeQuicksortxxx(a, l, p 1) } } } public void SafeQuicksortxxx(Comparable[] a) { SafeQuicksortxxx(a, 0, a.length 1); }

A stack overflow means that here are too many pending recursive calls. What is the maximum stack size for Quicksortxxx and for SafeQuicksortxxx given an input of size n? (Just state a Big-Theta expression for the stack size rather than an exact value).