/*
* @(#)EQSortAlgorithm.java 1.0 95/06/26 Jim Boritz
*
* Copyright (c) 1995 UBC Microsystems, Inc. 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 provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* UBC 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. UBC SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
/**
* An enhanced quick sort demonstration algorithm
* SortAlgorithm.java, Thu Oct 27 10:32:35 1994
*
* @author Jim Boritz
* @version 1.0, 26 Jun 1995
*/
/**
* 19 Feb 1996: Fixed to avoid infinite loop discoved by Paul Haberli.
* Misbehaviour expressed when the pivot element was not unique.
* -Jason Harrison
*
* 21 Jun 1996: Modified code based on comments from Paul Haeberli, and
* Peter Schweizer (Peter.Schweizer@mni.fh-giessen.de).
* Used Daeron Meyer's (daeron@geom.umn.edu) code for the
* new pivoting code. - Jason Harrison
*
* 09 Jan 1998: Another set of bug fixes by Thomas Everth (everth@wave.co.nz)
* and John Brzustowski (jbrzusto@gpu.srv.ualberta.ca).
*/
class EQSortAlgorithm extends SortAlgorithm {
void brute(int a[], int lo, int hi) throws Exception{
if ((hi-lo) == 1) {
if (a[hi] < a[lo]) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
pause();
}
}
if ((hi-lo) == 2) {
int pmin = a[lo] < a[lo+1] ? lo : lo+1;
pmin = a[pmin] < a[lo+2] ? pmin : lo+2;
if (pmin != lo) {
int T = a[lo];
a[lo] = a[pmin];
a[pmin] = T;
pause();
}
brute(a, lo+1, hi);
}
if ((hi-lo) == 3) {
int pmin = a[lo] < a[lo+1] ? lo : lo+1;
pmin = a[pmin] < a[lo+2] ? pmin : lo+2;
pmin = a[pmin] < a[lo+3] ? pmin : lo+3;
if (pmin != lo) {
int T = a[lo];
a[lo] = a[pmin];
a[pmin] = T;
pause();
}
int pmax = a[hi] > a[hi-1] ? hi : hi-1;
pmax = a[pmax] > a[hi-2] ? pmax : hi-2;
if (pmax != hi) {
int T = a[hi];
a[hi] = a[pmax];
a[pmax] = T;
pause();
}
brute(a, lo+1, hi-1);
}
}
void sort(int a[], int lo0, int hi0) throws Exception {
int lo = lo0;
int hi = hi0;
pause(lo, hi);
if ((hi-lo) <= 3) {
brute(a, lo, hi);
return;
}
/*
* Pick a pivot and move it out of the way
*/
int pivot = a[(lo + hi) / 2];
a[(lo + hi) / 2] = a[hi];
a[hi] = pivot;
while( lo < hi ) {
/*
* Search forward from a[lo] until an element is found that
* is greater than the pivot or lo >= hi
*/
while (a[lo] <= pivot && lo < hi) {
lo++;
}
/*
* Search backward from a[hi] until element is found that
* is less than the pivot, or hi <= lo
*/
while (pivot <= a[hi] && lo < hi ) {
hi--;
}
/*
* Swap elements a[lo] and a[hi]
*/
if( lo < hi ) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
pause();
}
}
/*
* Put the median in the "center" of the list
*/
a[hi0] = a[hi];
a[hi] = pivot;
/*
* Recursive calls, elements a[lo0] to a[lo-1] are less than or
* equal to pivot, elements a[hi+1] to a[hi0] are greater than
* pivot.
*/
sort(a, lo0, lo-1);
sort(a, hi+1, hi0);
}
void sort(int a[]) throws Exception {
sort(a, 0, a.length-1);
}
}
