import java.util.*;

public class QuickSort {
    public static void main(String args[]) {
        int[] arr = {25,23,141,241,512,321,521,12,312,4,125,1515};

        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    // This method sorts the array using quick sort algorithm
    // It works in the following way
    // 1- Partition the array:
    //      1. Pick an element in the current array and call it pivot.
    //      2. Put all the elements smaller than pivot before it, and all elements
    //          greater than pivot after it.
    //      3. By doing so, we can now know the correct index of pivot in the final sorted array
    //          and return it
    // 2- Now that we have the partition index (pivotIdx), repeat step 1 for the
    //      following 2 sub-arrays: low -> pivotIdx - 1, and pivotIdx + 1 -> high
    public static void quickSort(int[] arr, int low, int high){
        if(low < high){
            int pivotIdx = partition(arr, low, high);
            quickSort(arr, low, pivotIdx - 1);
            quickSort(arr, pivotIdx + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high){
        int pivot = arr[high];
        int i = low - 1;

        for(int j = low; j < high; j++){
            if(arr[j] <= pivot){
                i++;
                swap(arr, i, j);
            }
        }
        // Correct position of pivot is i + 1 because we placed the smaller elements
        // starting from low -> i
        swap(arr, i + 1, high);

        return i + 1;
    }

    // Methods that swaps two elements of an array
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}