function:RenderSidePart pageleftbodycaption pageleftbody sidenote Main.Quicksort-SideNote Main.SideNote Site.SideNote

# SimpleQuickSort.java

import java.util.ArrayList;
public class SimpleQuickSort {
/**
* Returns an array of n random integers
* from 1 to 10
* @param n is the size of the array desired
* @return an array of n random integers from 1 to 10
*/
private static ArrayList<Integer> randomArrayList(int n)
{
ArrayList<Integer> result = new ArrayList<Integer>();
return result;
}
/**
* sorts an int array
* @param a the array of integers, unsorted
* @return a sorted array of integers
*/
public static ArrayList<Integer> quickSort(ArrayList<Integer> a)
{
if (a.size()<=1) return a;
int halfway=a.size()/2;//the choice of the pivot is arbitrary
int pivot=a.get(halfway);
a.remove(halfway);
ArrayList<Integer> less=new ArrayList<Integer>();
ArrayList<Integer> more=new ArrayList<Integer>();
for(int i=0; i<a.size(); i++)
{
if (a.get(i)<pivot){
} else {
}
}
//Comment out the line below to hide the progress:
System.out.println("\n\tless ="+less+" (pivot="+pivot+") more="+more);

//Divide and conquer:
less=quickSort(less);
more=quickSort(more);
//Now we concatenate the result:
for (int i=0; i<more.size(); i++) less.add(more.get(i));
return less;

}

public static void main (String[] args){
ArrayList<Integer> a = randomArrayList(10);
System.out.println("Before sort:");
for (int item:a) System.out.print(item+" ");
long time=System.currentTimeMillis();

a = quickSort(a);

time=System.currentTimeMillis()-time;

System.out.println("\nAfter sort:");
for (int item:a) System.out.print(item+" ");
System.out.println("\nlapsed time:"+(time)+" milliseconds");
}

}


# QuickSorter.java


/**
* This is the "in place" version of Quicksort which is
* well suited for arrays.  The simple Version is easier
* to understand, but better suited for ArrayLists
* @author cct
*
*/
public class QuickSorter
{
private int[] a;
public QuickSorter(int[] anArray){
a=anArray;
}
public void sort(){
sort(0,a.length-1);
}
public void sort(int leftIndex, int rightIndex){

int i=leftIndex; // moves from left to center
int j=rightIndex; // moves from right to center
if(rightIndex<=leftIndex)
return;
int pivot=(i+j)/2; // the center index
while(i<=pivot && j>= pivot){

//Skip elements less than pivot
while (a[i] < a[pivot] && i<=pivot) i++;
//Skip elements greater than pivot
while (a[j] > a[pivot]&& j>=pivot) j--;
//swap the elements on the wrong side
if (i<j){
int x=a[i];
a[i]=a[j];
a[j]=x;
}
//Move toward the center
i++;
j--;
//change the pivot if the edge i or j
//matched the pivot and was swapped
if (i-1== pivot){
pivot = j+1;
j++;
}
if (j+1 == pivot){
pivot=i-1;
i--;
}
}
//Now recursively sort the left and right arrays
sort(leftIndex,pivot-1);
sort(pivot+1,rightIndex);
}

}


# SortTimer.java for comparing to Merge Sort

import java.util.Arrays;
import java.util.Scanner;

/**
This program measures how long it takes to sort an
array of a user-specified size with a certain
sort algorithm.
*/
public class SortTimer
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("Enter array size: ");
int n = in.nextInt();

// Construct random array

int[] a = ArrayUtil.randomIntArray(n, 100);
int[] b = (int[])a.clone();
//If you wanted to compare a third algorithm:
//int[] c = (int[])a.clone();

//If you wanted to see the unsorted array
//System.out.println(Arrays.toString(a));

MergeSorter mSorter = new MergeSorter(a);
QuickSorter qSorter = new QuickSorter(b);

// Use StopWatch to time the sort

StopWatch timer = new StopWatch();

timer.start();
mSorter.sort();
timer.stop();

System.out.println("Merge Sort Elapsed time: "
+ timer.getElapsedTime() + " milliseconds");
//If you wanted to see the sorted array
//System.out.println(Arrays.toString(a));
timer.reset();
timer.start();
qSorter.sort();
timer.stop();
System.out.println("Quick Sort Time:" + timer.getElapsedTime() +" milliseconds");
//If you wanted to see the array
//System.out.println(Arrays.toString(b));
}
}


SortTimer requires the ArrayUtil, StopWatch, and MergeSorter classes from the Chapter 14 Demos