1
2import java.util.*;
3class QuickSort {
4 //selects last element as pivot, pi using which array is partitioned.
5 int partition(int intArray[], int low, int high) {
6 int pi = intArray[high];
7 int i = (low-1); // smaller element index
8 for (int j=low; j<high; j++) {
9 // check if current element is less than or equal to pi
10 if (intArray[j] <= pi) {
11 i++;
12 // swap intArray[i] and intArray[j]
13 int temp = intArray[i];
14 intArray[i] = intArray[j];
15 intArray[j] = temp;
16 }
17 }
18
19 // swap intArray[i+1] and intArray[high] (or pi)
20 int temp = intArray[i+1];
21 intArray[i+1] = intArray[high];
22 intArray[high] = temp;
23
24 return i+1;
25 }
26
27
28 //routine to sort the array partitions recursively
29 void quick_sort(int intArray[], int low, int high) {
30 if (low < high) {
31 //partition the array around pi=>partitioning index and return pi
32 int pi = partition(intArray, low, high);
33
34 // sort each partition recursively
35 quick_sort(intArray, low, pi-1);
36 quick_sort(intArray, pi+1, high);
37 }
38 }
39}
40
41class QUICK_SORT{
42 public static void main(String args[]) {
43 //initialize a numeric array, intArray
44 int intArray[] = {3,2,1,6,5,4};
45 int n = intArray.length;
46 //print the original array
47 System.out.println("Original Array: " + Arrays.toString(intArray));
48 //call quick_sort routine using QuickSort object
49 QuickSort obj = new QuickSort();
50 obj.quick_sort(intArray, 0, n-1);
51 //print the sorted array
52 System.out.println("\nSorted Array: " + Arrays.toString(intArray));
53 }
54}