7227 : 퀵 정렬 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
퀵 정렬(Quick Sort)은 피봇(Pivot)을 기준으로 배열을 분할하고 재귀적으로 정렬하는 알고리즘입니다.
평균 시간 복잡도는 $O(N \log N)$이며, 최악의 경우 $O(N^2)$입니다.
피봇 선택 및 파티셔닝 전략에 따라 성능이 크게 달라집니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
평균 시간 복잡도는 $O(N \log N)$이며, 최악의 경우 $O(N^2)$입니다.
피봇 선택 및 파티셔닝 전략에 따라 성능이 크게 달라집니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
퀵 정렬 알고리즘을 구현하여 정렬된 배열을 한 줄에 공백으로 구분해 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6
3 6 8 10 1 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 6 8 10도움
중간 인덱스의 원소를 피봇으로 선택하거나 무작위 피봇을 사용하면 최악의 경우를 피할 수 있습니다. 이미 정렬된 배열에 대해 첫 원소를 피봇으로 삼으면 $O(N^2)$이 됩니다.