Video links

1. Simple Quicksort Explained
2. Quicksort with cards
3. In place Quicksort described by xoax.net
4. Bubble sort vs Quicksort
5. The Maggie Sort Algorithm

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>();
		for (int i=0;i<n;i++) result.add(1+(int)(10*Math.random()));
		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){
		        less.add(a.get(i));
		      } else {
		        more.add(a.get(i));
		      }
		}
		//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:
		less.add(pivot);
		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