In the QuickSort algorithm, the partition method we developed in class chose the start position for the pivot. We saw that this leads to worst case performance, O(n2), when the list is initially sorted. Try to improve your QuickSort by choosing the value at the middle, instead of the value at the start, for the pivot. Test your solution with the Driver you used for homework. Upload the output produced by the Driver, and your modified QuickSort source file.

ORIGINAL

public class QuickSort> implements Sorter

{

List list;

public void sort(List list)

{

this. list = list;

qSort(0, list. size() -1);

}

public void qSort(int start, int end)

{

if(start >= end)

return;

int p = partition(start, end);

qSort(start, p-1);

qSort(p+1,end);

}

public int partition(int start, int end)

{

int p = start;

E pivot = list. get(p);

for(int i = start+1; i <= end; i++)

if(pivot. compareTo(list. get(i)) > 0)

{

list. set(p, list. get(i));

p++;

list. set(i, list. get(p));

}

list. set(p, pivot);

return p;

}

}



Driver

public class DriverQuicksort

{ static final int MAX = 20;

public static void main(String[] args)

{

Random rand = new Random(); // random number generator

List numbers = new ArrayList ();

Sorter sorter;

sorter = new QuickSort ();

// Test QuickSort with random input

System. out. println ("Testing Quicksort");

for (int i=0; i
numbers. add (rand. nextInt(50)); // random int in [0..49]

System. out. println ("Before sorting:");

System. out. println (numbers);

sorter. sort (numbers );

System. out. println ("After sorting:");

System. out. println (numbers);

System. out. println ();

// Test QuickSort with ascending input

numbers. clear();

for (int i=0; i
numbers. add (i * 10); // initially in ascending order

System. out. println ("Before sorting:");

System. out. println (numbers);

sorter. sort ( numbers);

System. out. println ("After sorting:");

System. out. println (numbers);

System. out. println ();

// Test QuickSort with descendng input

numbers. clear();

for (int i=0; i
numbers. add (MAX-i); // initially in ascending order

System. out. println ("Before sorting:");

System. out. println (numbers);

sorter. sort ( numbers);

System. out. println ("After sorting:");

System. out. println (numbers);

System. out. println ();

numbers. clear();

numbers. add(75);

numbers. add(93);

numbers. add(35);

numbers. add(0);

numbers. add(75);

numbers. add(-2);

numbers. add(93);

numbers. add(4);

numbers. add(6);

numbers. add(76);

System. out. println ("Before sorting:");

System. out. println (numbers);

sorter. sort(numbers);

System. out. println ("After sorting:");

System. out. println (numbers);

System. out. println ();

}

}