import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println("Before:");
        System.out.println(Arrays.toString(array));

        quickSort(array, 0, array.length - 1);

        System.out.println("After:");
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array, int low, int high) {
        // Base case: if array has less than 2 elements, it's already sorted
        if (low >= high) {
            return;
        }

        // Partition the array and get the pivot index
        int pivotIndex = partition(array, low, high);

        // Recursively sort left part (before pivot)
        quickSort(array, low, pivotIndex - 1);

        // Recursively sort right part (after pivot)
        quickSort(array, pivotIndex + 1, high);
    }

    public static int partition(int[] array, int low, int high) {
        // Select the last element as pivot
        int pivot = array[high];

        // Index for smaller element (where pivot will be placed)
        int i = low - 1;

        // Walk through array comparing elements with pivot
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (array[j] <= pivot) {
                i++;
                // Swap elements: place smaller element to the left
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // Place pivot in its correct position
        i++;
        int temp = array[i];
        array[i] = array[high];
        array[high] = temp;

        // Return pivot index
        return i;
    }
}