Challenge: Write Quick Sort

Lab C++ Intermediate 20 points

Sort n numbers with your own in-place quick sort using the Lomuto partition (last item as pivot).

Input

Line 1: n. Line 2: n whole numbers.

Output

The sorted numbers.

Example

Input

6
10 7 8 9 1 5

Output

1 5 7 8 9 10

Sample input available Sample output available

Editor

C++

Hints

partition puts smaller items before the pivot and returns the pivot's final index.

Recurse on both sides.

Solution explanation

After each partition the pivot is in its final place.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int part(vector<int>& a, int lo, int hi) {
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);
    return i;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = part(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    quickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Output

Answer