/*
* file: ~/public_html/java/Q2SortAlgorithm.java
*
* Created by Ola Martensson, dat92omaludat.lth.se
*
* Time-stamp: <96/03/07 10:43:14 dat92oma@ludat.lth.se>
*
*
* Quick hack to implement n*log(n), but with better "worst
* case", algorithm "Randomized Quicksort"
*/
class Q2SortAlgorithm extends SortAlgorithm
{
private void exchange(int a[],int x, int y) {
int t=a[x];
a[x]=a[y];
a[y]=t;
}
private int partition(int a[], int p,int r) throws Exception {
int x=a[p];
int i=p-1;
int j=r+1;
pause(p,r);
while(true) {
--j;
for(;a[j] > x;--j)
;
++i;
for(;a[i] < x;++i)
;
if(i