/*
* @(#)QSortAlgorithm.java 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 http://www.javasoft.com/copy_trademarks.html
* for further important copyright and trademark information and to
* http://www.javasoft.com/licensing.html 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
* SortAlgorithm.java
*
* @author James Gosling
* @author Kevin A. Smith
* @version @(#)QSortAlgorithm.java 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.
* <fuhrmann@cs.tu-berlin.de>
*/
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);
}
}
