Description

Given a positive integer sequence of size n. Please sort the sequence in ascending order via quick sort.

The following is the pseudocode for the algorithm:

quickSort(array, leftmostIndex, rightmostIndex)
 if (leftmostIndex < rightmostIndex)
   pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
   quickSort(array, leftmostIndex, pivotIndex - 1)
   quickSort(array, pivotIndex, rightmostIndex)
​
partition(array, leftmostIndex, rightmostIndex)
 set rightmostIndex as pivotIndex
 storeIndex <- leftmostIndex - 1
 for i <- leftmostIndex + 1 to rightmostIndex
 if element[i] < pivotElement
   swap element[i] and element[storeIndex]
   storeIndex++
 swap pivotElement and element[storeIndex+1]
return storeIndex + 1

 

Input

$n$: the size of the sequence. $1 \leq n \leq 10^5$

$a_i$: the element of the sequence. $1 \leq n \leq 10^8$

Output

Print the sorted sequence.

Note:

• Elements are separated by a single whitespace character.

• There is no trailing whitespace in the last element.

• You should append a newline character(\n) after the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss