QuickSort.java

import java.util.Arrays;

public class QuickSort {

public static void main(String[] args) {

int[] A = {4,9,12,21,32,12,32,65,2,4,5,7,1,2,3,6,98,12,323,54};

System.out.println("Before sort, the array is " + Arrays.toString(A));

sort(A);

System.out.println("After sort, the array is " + Arrays.toString(A));

}

public static void sort(int[] A) {

sort(A, 0, A.length - 1);

}

private static void sort(int[] A, int p, int r) {

if (p < r) {

int q = partion(A, p, r);

sort(A, p, q - 1);

sort(A, q + 1, r);

}

}

private static int partion(int[] A, int p, int r) {

int x = A[r];

int i = p - 1;

for (int j = p; j <= r - 1; j++) {

if (A[j] <= x) {

i = i + 1;

int tmp = A[j];

A[j] = A[i];

A[i] = tmp;

}

}

int tmp = A[i + 1];

A[i + 1] = A[r];

A[r] = tmp;

return i + 1;

}

}