Time Limit: 1s
Memory Limit: 128MB
퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다.
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
전체 배열을
부분배열1. Pivot(피벗)보다 작은 값들을 저장한 배열
부분배열2. Pivot과 같은 값들을 저장한 배열
부분배열3. Pivot보다 큰 값들을 저장한 배열
세 개로 나누어 부분배열 1과 부분배열 3을 재귀적으로 다시 정렬하면 된다.
Pivot 선택 순서와 Quick sort로 배열을 오름차순으로 정렬한 결과를 구해보자.
Pivot은 배열의 아무 요소나 정해도 상관없지만, 이 문제에서는 배열의 첫 번째 요소를 Pivot으로 한다.
어떤 것을 먼저 정렬하든 상관 없으나 이 문제에서는 부분배열1을 정렬하고 난 후, 부분배열3를 정렬한다.
* Line 1 : 정렬할 배열 갯수 N (1≤N≤1000)
* Line 2~N+1 : 배열 arr의 크기 n이 입력되고 그 뒤로 배열 arr의 원소들이 공백으로 구분되어 입력된다. (1 ≤ n ≤ 100, -2000 ≤ arr[i] ≤ 2000)
* Line 1~N : 정렬 중의 Pivot 선택 순서와 정렬 결과를 "/"로 구분하여 한 줄로 출력한다.
3 3 0 2 1 4 4 3 2 1 10 5 7 2 4 1 3 0 8 6 5
0 2 / 0 1 2 4 3 2 / 1 2 3 4 5 2 1 4 7 / 0 1 2 3 4 5 5 6 7 8
{5, 7, 2, 4, 1, 3, 0, 8, 6, 5} Pivot 5 -> {2, 4, 1, 3, 0}{5, 5}{7, 8, 6}
{2, 4, 1, 3, 0} Pivot 2 -> {1, 0}{2}{4, 3}
{1, 0} Pivot 1 -> {0}{1}
{4, 3} Pivot 4 -> {3}{4}
->{0}{1}{2}{3}{4}
{7, 8, 6} Pivot 7 -> {6}{7}{8}
->{6}{7}{8}
-> {0}{1}{2}{3}{4}{5, 5}{6}{7}{8}
* 대부분의 언어에는 quick sort가 내장되어있다. 앞으로 나올 문제들에서 알차게 써먹어보자.
C, C++: qsort(<stdlib.h>)
C++: sort(<algorithm>)
Java: Arrays.sort(java.util.arrays)
Python: sorted