퀵정렬 구현하기

문제

N개의 자연수가 주어질 때, 퀵정렬을 이용하여 이를 정렬하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄에 N개의 자연수가 주어진다.  

출력

퀵정렬을 이용하여 숫자를 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10

5 9 2 8 3 7 4 6 1 10

예제 출력

1 2 3 4 5 6 7 8 9 10

예제 입력

5

2 3 1 2 1

예제 출력

1 1 2 2 3

 

#코드

import sys
 
def quick_sort(arr):
  if len(arr) <= 1:
    return arr
  else:
    pivot = arr[0]
    tail  = arr[1:]
    
    left  = [x for x in tail if pivot >= x]
    right = [x for x in tail if pivot < x]
    
    return quick_sort(left) + [pivot] + quick_sort(right)
  
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n   = int(input())
  arr = list(map(int, input().split()))
  
  print(*quick_sort(arr))