question about quicksort 3 way partition
- by davit-datuashvili
i want implement quicksort 3 way partition here is code
public class quick3{
public static void quicksort3(int a[],int l,int r){
int k;
int v=a[r];
if (r<=l) return;
int i=l;
int j=r;
int p=l-1;
int q=r;
for (;;)
{
while (a[++i]<v);
while (v<a[--j]) if (j==i) break;
if (i>=j) break;
swap( a,i, j);
if (a[i]==v){ p++; swap(a,p,i);}
if (v==a[j]){ q--; swap( a,q,j);
}
}
swap(a,i,r);
j=i-1;
i=i+1;
for (k=1;k<=p;k++,j--) swap(a,k,j);
for (k=r-1;k>=q;k--,i++) swap(a,k,i);
quicksort3(a,l,j);
quicksort3(a,i,r);
}
public static void main(String[]args){
int a[]=new int[]{4,6,5,9,7,8,3};
quicksort3(a,0,a.length-1);
for (int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
public static void swap(int a[],int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
after change result is
4
8
7
6
3
5
9
any suggestion?please help
