Quick Sort Algorithm | Java Programs

Output:

*** Quick Sort Algorithm ***

--- Array Before ---
52, 45, 7, 9, 86, 12, 5, 1, 

--- Array After ---
1, 5, 7, 9, 12, 45, 52, 86,

Click Here For Java Online Compiler

Solution:

/**
 *
 * Source Code Taken from : http://www.vogella.com
 */
public class QuickSort {

    private int[] numbers;
    private int number;

    public void sort(int[] values) {
        this.numbers = values;
        number = values.length;
        quicksort(0, number - 1);
    }

    private void quicksort(int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        int pivot = numbers[(low + high) / 2];

        // Divide into two lists
        while (i <= j) {
            // If the current value from the left list is smaller then the pivot
            // element then get the next element from the left list
            while (numbers[i] < pivot) {
                i++;
            }
            // If the current value from the right list is larger then the pivot
            // element then get the next element from the right list
            while (numbers[j] > pivot) {
                j--;
            }

            // If we have found a values in the left list which is larger then
            // the pivot element and if we have found a value in the right list
            // which is smaller then the pivot elment then we exchange the
            // values.
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }

        }
        // Recursion
        if (low < j) {
            quicksort(low, j);
        }
        if (i < high) {
            quicksort(i, high);
        }
    }

    private void exchange(int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    public static void main(String[] args) {
        QuickSort q = new QuickSort();
        System.out.println("*** Quick Sort Algorithm ***" + "\n");
        System.out.println("--- Array Before ---");
        int a[] = {52, 45, 7, 9, 86, 12, 5, 1};
        for (int i : a) {
            System.out.print(i + ", ");
        }
        q.sort(a);
        System.out.println("\n");
        System.out.println("--- Array After ---");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");

        }
    }
}