#include <iostream>
using namespace std;

int Partition(int arr[], int l, int h) {
    int pivot = arr[l]; // Choose the pivot
    int i = l + 1; // Start i from the next element
    int j = h;

    while (i <= j) { // Change condition to include equal case
        // Move i to the right until we find an element greater than the pivot
        while (i <= h && arr[i] <= pivot) {
            i++;
        }

        // Move j to the left until we find an element less than the pivot
        while (arr[j] > pivot) {
            j--;
        }

        // Swap elements if i is less than j
        if (i < j) {
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[l], arr[j]); // Move pivot to the correct position
    return j; // Return the partition index
}

void quickSort(int arr[], int l, int h) {
    if (l < h) {
        int j = Partition(arr, l, h); // Call to Partition function
        quickSort(arr, l, j - 1); // Sort the left part
        quickSort(arr, j + 1, h); // Sort the right part
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5}; // Added an extra element for better testing
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements
    quickSort(arr, 0, n - 1); // Call quickSort
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "; // Output the sorted array
    }
    cout << endl; // Newline for better output formatting
    return 0;
}