quick sort code in java

Solutions on MaxInterview for quick sort code in java by the best coders in the world

showing results for - "quick sort code in java"
Nicola
07 May 2016
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}