Quick Sort

Lab Python Advanced 30 points

Implement quick sort using the first element as pivot and list comprehensions for the partitions. Print the sorted list.

Input

One line of integers.

Output

One line.

Example

Input

3 6 8 10 1 2 1

Output

1 1 2 3 6 8 10

Sample input available Sample output available

Editor

Python

Hints

Items smaller than the pivot go left, the rest go right.

Solution explanation

Quick sort averages O(n log n) but degrades to O(n²) on already-sorted input with this pivot choice.

Show solution

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot, rest = a[0], a[1:]
    return quick_sort([x for x in rest if x < pivot]) + [pivot] + quick_sort([x for x in rest if x >= pivot])


print(*quick_sort(list(map(int, input().split()))))

Output

Answer