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 ();
}
}
