7279 : 재귀 퀵정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
퀵 정렬을 재귀 함수로 구현하십시오.
피봇을 선택하고 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할한 후 각각 재귀 호출합니다.
평균 시간 복잡도: $O(N \log N)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
피봇을 선택하고 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할한 후 각각 재귀 호출합니다.
평균 시간 복잡도: $O(N \log N)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 크기 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
재귀 퀵 정렬로 정렬한 오름차순 배열을 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6
3 6 8 10 1 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 6 8 10도움
def quick_sort(arr): if len(arr)<=1: return arr; pivot=arr[len(arr)//2]; return quick_sort([x for x in arr if x<pivot]) + [x for x in arr if x==pivot] + quick_sort([x for x in arr if x>pivot])