Challenge: Write Quick Sort

Lab Python Intermediate 20 points

Read a list of numbers and sort it with your own in-place quick sort using the Lomuto partition (last item as the pivot). Print the sorted numbers separated by spaces.

Input

One line of whole numbers.

Output

The sorted numbers.

Example

Input

10 7 8 9 1 5

Output

1 5 7 8 9 10

Sample input available Sample output available

Editor

Python

Hints

partition() puts everything smaller than the pivot on its left and returns the pivot's final index.

Then quick sort the part before the pivot and the part after it.

Solution explanation

After each partition the pivot is in its final place, and the two sides are sorted separately.

Show solution

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

def quick_sort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)
        quick_sort(a, lo, p - 1)
        quick_sort(a, p + 1, hi)

a = list(map(int, input().split()))
quick_sort(a, 0, len(a) - 1)
print(" ".join(map(str, a)))

Output

Answer