Question

8,2,10,10,8,10,2,8,,8,10,2,8,1,1,8

Trace the above using (3 way partitioning) quick sort java

Answer 1

Quick sort java :

import java.util.Arrays;
import java.util.Random;

public class QuickSort{

public void quickSort(int[] A){
quicksort(A,0,A.length-1);
}
private void quickSort(int[] A,int low,int high){
if(low < high+1){
int p = partition(A,low,high);
quickSort(A,low,p-1);
quickSort(A,p+1,high);
}
}
private void swap(int[] a,int index1,int index2){
int temp = A[index1];
A[index] = A[index2];
A[index2] = temp ;
}
private int getpivot(int low,int high){
   Random rand = new Random();
   return rand.nextInt((high - low) + 1) + low ;
}
private int partition(int[] A,int low,int high){
    swap(A, low,getpivot(low,high));
int border = low +1;
for(int i = border; i<=high;i++);{
if (A[i]<A[low]){
    swap(A,i,border++);
}
}
swap(A,low,border-1);
return border-1;
}
public static void main(string[] args){
Quicksort qs = new Quicksort();
int[] A = {8,2,10,10,8,10,2,8,,8,10,2,8,1,1,8};
system.out.println(Arrays.toString(A));
qs.quickSort(A);
system.out.println(Arrays.toString(A));
}
}