public class _4 {
    public static void main(String[] args) {
        int arr[] = {4, 6, 2, 5, 7, 9, 1, 3};
        int low = 0;
        int high = arr.length - 1;

        quickSort(arr, low, high);

        System.out.println("Sorted array:");
        for (int e : arr) {
            System.out.print(e + " ");
        }
    }

    static void quickSort(int arr[], int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);
            quickSort(arr, low, partitionIndex - 1);  // Sort the left subarray
            quickSort(arr, partitionIndex + 1, high); // Sort the right subarray
        }
    }

    static int partition(int arr[], int low, int high) {
        int pivot = arr[low]; // Choose the pivot as the first element
        int i = low;
        int j = high;

        while (i < j) {
            // Increment i until an element greater than the pivot is found
            while (i < high && arr[i] <= pivot) {
                i++;
            }
            // Decrement j until an element smaller than or equal to the pivot is found
            while (j > low && arr[j] > pivot) {
                j--;
            }

            // Swap elements if i and j haven't crossed
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap pivot with arr[j] to put it in its correct position
        int temp = arr[low];
        arr[low] = arr[j];
        arr[j] = temp;

        return j; // Return the partition index
    }
}