#include <iostream>
using namespace std;

bool quickSort(int arr[], int first, int last) {
    if (first < last) {
        int pivot = first;
        int i = first;
        int j = last;
        int temp;
        while (i < j) 
        {
            while (arr[i] <= arr[pivot] && i < last)
                i++;
            while (arr[j] > arr[pivot])
                j--;
            if (i < j) 
            {
                swap(arr[i],arr[j]);
            }
        }
        swap(arr[pivot],arr[j]);
        bool leftSorted = quickSort(arr, first, j - 1);
        bool rightSorted = quickSort(arr, j + 1, last);
        return leftSorted && rightSorted;
    }
    return true;
}

int main() {
    int arr[] = {9,3,4,2,1,8};
    int n = 6;

    bool sorted = quickSort(arr, 0, n - 1);

    if (sorted) {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
    } else {
        cout << "Error: Sorting failed";
    }

    return 0;
}