quick sort

#include <iostream>
#include <vector>

using namespace std;

vector<int> quickSort(const vector<int>& arr) {
    int pivot = arr[0];
    vector<int> left, middle, right;

    // Partitioning the array
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < pivot) {
            left.push_back(arr[i]);
        } else {
            right.push_back(arr[i]);
        }
    }

    middle.push_back(pivot); // Add the pivot to the middle
    // Combine left, middle, and right
    left.insert(left.end(), middle.begin(), middle.end());
    left.insert(left.end(), right.begin(), right.end());

    return left;
}

int main() {
    int n;
    cin >> n; // Size of the array
    vector<int> arr(n);
    
    // Input array
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // Get the partitioned array
    vector<int> result = quickSort(arr);

    // Output the result
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}