Here is the code with out HTML formatting. Save it to a file.

/* * @(#) 1.3 29 Feb 1996 James Gosling * * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved. * * Permission to use, copy, modify, and distribute this software * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and * without fee is hereby granted. * Please refer to the file * for further important copyright and trademark information and to * for further important * licensing information for the Java (tm) Technology. * * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. * * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR * HIGH RISK ACTIVITIES. */ /** * A quick sort demonstration algorithm * * * @author James Gosling * @author Kevin A. Smith * @version @(#) 1.3, 29 Feb 1996 * extended with TriMedian and InsertionSort by Denis Ahrens * with all the tips from Robert Sedgewick (Algorithms in C++). * It uses TriMedian and InsertionSort for lists shorts than 4. * <> */ public class FastQSortAlgorithm extends SortAlgorithm { /** This is a generic version of C.A.R Hoare's Quick Sort * algorithm. This will handle arrays that are already * sorted, and arrays with duplicate keys.<BR> * * If you think of a one dimensional array as going from * the lowest index on the left to the highest index on the right * then the parameters to this function are lowest index or * left and highest index or right. The first time you call * this function it will be with the parameters 0, a.length - 1. * * @param a an integer array * @param lo0 left boundary of array partition * @param hi0 right boundary of array partition */ private void QuickSort(int a[], int l, int r) throws Exception { int M = 4; int i; int j; int v; if ((r-l)>M) { i = (r+l)/2; if (a[l]>a[i]) swap(a,l,i); // Tri-Median Methode! if (a[l]>a[r]) swap(a,l,r); if (a[i]>a[r]) swap(a,i,r); j = r-1; swap(a,i,j); i = l; v = a[j]; for(;;) { while(a[++i]<v); while(a[--j]>v); if (j<i) break; swap (a,i,j); pause(i,j); if (stopRequested) { return; } } swap(a,i,r-1); pause(i); QuickSort(a,l,j); QuickSort(a,i+1,r); } } private void swap(int a[], int i, int j) { int T; T = a[i]; a[i] = a[j]; a[j] = T; } private void InsertionSort(int a[], int lo0, int hi0) throws Exception { int i; int j; int v; for (i=lo0+1;i<=hi0;i++) { v = a[i]; j=i; while ((j>lo0) && (a[j-1]>v)) { a[j] = a[j-1]; pause(i,j); j--; } a[j] = v; } } public void sort(int a[]) throws Exception { QuickSort(a, 0, a.length - 1); InsertionSort(a,0,a.length-1); pause(-1,-1); } }

Return to Sorting Algorithms Demo