퀵 정렬
- 퀵 정렬은 분할 정복 알고리즘으로 분류
- 퀵 정렬 알고리즘은 문제를 2개의 부분 문제로 분할
퀵 정렬의 아이디어
퀵 정렬은 피봇(pivot)이라 일컫는 배열의 원소(숫자)를
기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰
숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에
놓는다.
퀵 정렬은 분할된 부분문제들에 대해서도 위와 동일한
과정을 순환으로 수행하여 정렬
피봇
피봇은 분할된 왼편이나 오른편 부분에 포함되지 않음
알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
QuickSort(A, left, right)
입력: 배열 A[left]~A[right]
출력: 정렬된 배열 A[left]~A[right]
1. if (left < right) {
2. 피봇을 A[left]~A[right]에서 선택하고,
피봇을 A[left]와 자리를 바꾼 후, 피봇과 배열의
각
원소를 비교하여 피봇보다 작은 숫자들은
A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자들은
A[p+1]~A[right]로 옮기며, 피봇은 A[p] 에
놓는다.
3. QuickSort(A, left, p-1) // 피봇보다 작은 그룹
4. QuickSort(A, p+1 right) // 피봇보다 큰 그룹
}
위의 알고리즘을 이용한 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 7, 1, 10, 6, 9};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] A, int left, int right) {
if (left < right) {
int p = partition(A, left, right);
quickSort(A, left, p - 1);
quickSort(A, p + 1, right);
}
}
private static int partition(int[] A, int left, int right) {
int pivot = A[left];
int i = left + 1;
int j = right;
while (i <= j) {
if (A[i] <= pivot) {
i++;
} else if (A[j] > pivot) {
j--;
} else {
swap(A, i, j);
}
}
swap(A, left, j);
return j;
}
private static void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
하지만 자바 라이브러리를 이용해서 코드를 작성하면 간략하게 만들수 있디.
1
2
3
4
5
6
7
8
9
10
11
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 7, 1, 10, 6, 9};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
정리
- 퀵 정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘이다.
- 퀵 정렬은 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보인다.
- 생물 정보 공학(Bioinformatics)에서 특정 유전자를 효율적으로 찾는데 접미 배열(suffix array)과 함께 퀵 정렬이 활용된다
선택 문제
선택 문제는 n개의 숫자들 중에서 k 번째로 작은 숫자를 찾는 문제 단순한 알고리즘
- 최소 숫자를 k 번 찾는다.
- 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거한다.
- 숫자들을 정렬한 후, k번째 숫자를 찾는다.
- 위의 알고리즘들은 각각 최악의 경우 O(kn)과 O(nlogn)의 수행 시간이 걸린다.
