/****************************************************************************** Quicksort observable ---------------------------------------------------- Copyright (c) Gunnar Gotshalks. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for NON-COMMERCIAL purposes and without fee is hereby granted. *******************************************************************************/ package FlexOr.searchAndSort; import FlexOr.container.*; import java.awt.Color; /** Sort an array of objects using quicksort.
@author Gunnar Gotshalks @version 1.0 1999 Jan 15 */ public class QuicksortObs extends SortObservable implements ArraySort { public QuicksortObs(final Object[] array, final BinaryPredicate bp) { super(array, bp); } /** @param array Array of elements to be sorted. @param bp Defines how array elements are compared. */ public void sort(final Object[] array, final BinaryPredicate bp) { execute(array, bp); } /** The quicksort method.
Loop invariant:
???@param array Array of elements to be sorted. @param bp Defines how array elements are compared. */ public void execute(final Object[] array, final BinaryPredicate bp) { quicksort(array, 0, array.length-1, bp); } private void quicksort(final Object[] array, final int lowerIndex, final int upperIndex, final BinaryPredicate bp) { if (lowerIndex >= upperIndex) { if (lowerIndex == upperIndex) sod.tag[lowerIndex] = Color.black; return; } Object pivotValue = array[lowerIndex], tmp; int splitIndex = lowerIndex; sod.tag[lowerIndex] = Color.magenta; for (int i = lowerIndex+1 ; i <= upperIndex ; i++) { // Comparison -- Added to make the sort observable. >>>> setChanged(); sod.tag[i] = Color.magenta; sod.swap = false; notifyObservers(sod); try { synchronized(this) { wait(); } } catch (InterruptedException e) {} // <<<< if (bp.execute(array[i], pivotValue)) { splitIndex++; // Swap -- Added to make the sort observable. >>>> setChanged(); sod.tag[i] = Color.cyan; sod.tag[splitIndex] = Color.cyan; sod.swap = true; notifyObservers(sod); try { synchronized(this) { wait(); } } catch (InterruptedException e) {} sod.tag[i] = Color.gray; sod.tag[splitIndex] = Color.lightGray; // <<<< tmp = array[splitIndex]; array[splitIndex] = array[i]; array[i] = tmp; } else { sod.tag[i] = Color.gray; } } // Swap -- Added to make the sort observable. >>>> setChanged(); sod.tag[lowerIndex] = Color.cyan; sod.tag[splitIndex] = Color.cyan; sod.swap = true; notifyObservers(sod); try { synchronized(this) { wait(); } } catch (InterruptedException e) {} for (int k = lowerIndex ; k <= upperIndex ; k++) { sod.tag[k] = Color.gray; } sod.tag[splitIndex] = Color.black; // <<<< tmp = array[splitIndex]; array[splitIndex] = pivotValue; array[lowerIndex] = tmp; if (splitIndex - lowerIndex > upperIndex - splitIndex) { quicksort(array, splitIndex+1, upperIndex, bp); quicksort(array, lowerIndex, splitIndex-1, bp); } else { quicksort(array, lowerIndex, splitIndex-1, bp); quicksort(array, splitIndex+1, upperIndex, bp); } } }