Quick Sort

Lab C Advanced 30 points

Implement recursive quick sort (Lomuto partition, last element as pivot) on n ≤ 50 integers and print the result.

Input

Line 1: n. Line 2: n integers.

Output

One line.

Example

Input

7
3 6 8 10 1 2 1

Output

1 1 2 3 6 8 10

Sample input available Sample output available

Editor

Hints

Partition: everything smaller than the pivot goes left of it.

Then sort the two sides recursively.

Solution explanation

Quick sort averages O(n log n); the standard library's qsort is usually a variant of it.

Show solution

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void quick_sort(int *a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            swap(&a[i], &a[j]);
            i++;
        }
    }
    swap(&a[i], &a[hi]);
    quick_sort(a, lo, i - 1);
    quick_sort(a, i + 1, hi);
}

int main() {
    int n, a[50];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    quick_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d%s", a[i], i < n - 1 ? " " : "\n");
    return 0;
}

Output

Answer