APS105 Sorting Demo Page

SelectionSort

Below, you should see the black selection sort window.
Each row represents an integer number, with larger numbers being drawn farther to the right.
Click anywhere in window to watch the selection sort take a step towards sorting the rows.
With each step, the yellow bar keeps track of how far along the sorting has progressed.
The value in the yellow row is compared to the green box.
If the the yellow row is smaller, it becomes the green box.
Each step, the yellow row advances to the next row.
Eventually the smallest remaining value is found, selectioned, and swapped with the value in the gray bar.
The gray bar then advances down and the process is repeated.
Eventually only one row remains, so sorting is done.

Bubblesort

Below, you should see the black bubblesort window.
Each row represents an integer number, with larger numbers being drawn farther to the right.
Click anywhere in window to watch the bubblesort take a step towards sorting the rows.
With each step, the green bar keeps track of how far along the sorting has progressed.
The value in the green row is compared to the next row.
If the the green row is larger, the rows are swapped.
Each step, the green row advances to the next row.
This brings the largest value seen so far to the bottom of the screen,
and is like a bubble "floating" to the bottom.

Bubblesort also involves a number of passes.
When the green row reaches the bottom row, a new pass is begun.
After each pass, one more row on the bottom is in the correct sorted order.
We can be a bit more efficient and not step over these lower rows when advancing the green bar.
To illustrate the correctly sorted rows seen so far, a white line is drawn.
The white line moves up until the rows are guaranteed to be completely sorted.

Java code which accomplishes a bubble sort looks something like this:

    int[] array = { 3, 6, 9, 13, 1, 19, 6, 11, 2, 18, 16 };

    for( int pass = 0;  pass < array.length; pass++ ) {

	// 'pass' tells us how many rows at the bottom
	// are guaranteed to be sorted

        for( int greenrow = 0;
             greenrow < array.length - pass;
             greenrow++ )
        {
            drawGraphics();
            if( greenrow < array.length-1
                && array[greenrow] > array[greenrow+1] )
            {
                // green row is bigger, swap the two rows
                int temp = array[greenrow];
                array[greenrow]   = array[greenrow+1];
                array[greenrow+1] = temp;
            }
        }

    }

Quicksort

Below, you should see the quicksort window.
Click in the window to single-step the program.
You make your browser window wide to see the whole thing.

	class QuickSort
	{
		public static void main( String[] args )
		{
			int[] array = { 8, 6, 9, 13, 1, 17, 6, 19, 2, 18, 16 };
			qsort( array );
		}

		public static void qsort( int[] array )
		{
			sortSubArray( array, 0, array.length-1 );
		}

		private static void sortSubArray( int[] array, int lower, int upper )
		{
			if( lower >= upper ) 
				return;

			// find the pivot value
			// use the array[lower] point as the pivot
			final int pivot = array[lower];

			int mid = lower;

			// scan the sub-array from lower to upper,
			//      partitioning it to 2 groups.
			// move values <  p to positions <=mid in the array
			// keep values >= p at positions  >mid in the array
			for( int i=lower+1; i <= upper; i++ ) {
				if( array[i] < pivot ) {
					mid++;
					swap( array, mid, i );
				}
			}

			// move the pivot to the correct position
			swap(  array, lower, mid );

			// recursively sort the partitions
			sortSubArray( array, lower, mid-1 );
			sortSubArray( array, mid+1, upper );
		}

		private static void swap( int[] array, int i, int j )
		{
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}