특정한 값(피벗)을 기준으로 큰 숫자와 작은 숫자를 두 집합으로 나누어 나눈다.
퀵 정렬은 대표적인 '분할 정복' 알고리즘이다.
예시 문제:
3 10 5 4 1 2 9 6 7 8
해당 숫자를 오름차순으로 정렬하시오.
일반적으로 퀵 정렬에서 가장 앞에 있는 값을 Pivot으로 설정한다.
이 피벗 값을 왼쪽에서 오른쪽으로 이동하며 피벗 값 보다 큰 첫 수를 찾고, 오른쪽에서 왼쪽으로 이동하며 피벗 값보다 작은 첫 수를 찾아 두 개의 자리를 바꾼다.
3 10 5 4 1 2 9 6 7 8
1번째 수행:
피벗 값 = 3
왼쪽 -> 오른쪽으로 비교, 3보다 큰 첫 수 = 10
오른쪽 -> 왼쪽으로 비교, 3보다 작은 첫 수 = 2
이 두 개의 자를 바꾸어 준다.
3 2 5 4 1 10 9 6 7 8
이어서 연산.
피벗 값 = 3
왼쪽 -> 오른쪽으로 비교, 3보다 큰 첫 수 = 5
오른쪽 -> 왼쪽으로 비교, 3보다 작은 첫 수 = 1
이 두 개의 자를 바꾸어 준다.
3 2 1 4 5 10 9 6 7 8
2번째 수행:
여기에서는 위와 같은 규칙에 따를 수 없게 왼쪽 -> 오른쪽 비교와 오른쪽 -> 왼쪽의 비교가 엇갈린다. 이 때에는 엇갈린 위치에서 작은 숫자와 피벗 값의 자리를 교체해 준다. 그러면 해당 피벗 값의 위치는 제자리를 찾은 것으로 간주되어 위치가 고정된다. (왼쪽은 3보다 모두 작고, 오른쪽은 3보다 모두 크다. 로 분할된다.)
1 2 3 4 5 10 9 6 7 8
3번째 수행:
이어서 왼쪽과 오른쪽의 맨 앞의 숫자를 피벗 값으로 설정한다.
피벗 값 = 1
1 2 3 4 5 10 9 6 7 8
왼쪽 연산:
피벗 값 = 1
왼쪽-> 오른쪽(피벗 값 전까지) 연산 했을 때 자신보다 작은 값이 존재하지 않는다. 그러면 자기 자신과 자리를 교체하며 위치가 고정된다.
오른쪽 연산:
피벗 값 = 4
왼쪽-> 오른쪽(피벗 값 전까지) 연산 했을 때 자신보다 작은 값이 존재하지 않는다. 그러면 자기 자신과 자리를 교체하며 위치가 고정된다.1 2 3 4 5 10 9 6 7 8
4번째 수행:
왼쪽 연산:
피벗 값 = 2
왼쪽-> 오른쪽(피벗 값 전까지) 연산 했을 때 자신보다 작은 값이 존재하지 않는다. 그러면 자기 자신과 자리를 교체하며 위치가 고정된다.
오른쪽 연산:
피벗 값 = 5
왼쪽-> 오른쪽(피벗 값 전까지) 연산 했을 때 자신보다 작은 값이 존재하지 않는다. 그러면 자기 자신과 자리를 교체하며 위치가 고정된다.1 2 3 4 5 10 9 6 7 8
5번째 수행:
왼쪽 연산: 연산할 게 없다.
오른쪽 연산:
피벗 값 = 10
왼쪽-> 오른쪽 비교 없음.
오른쪽 -> 왼쪽 비교 = 8
피벗 값과 8 자리 교체1 2 3 4 5 8 9 6 7 10
6번째 수행:
피벗 값 = 8
왼쪽 -> 오른쪽 비교, 9
오른쪽 -> 왼쪽 비교, 7
9와 7 자리 교체.
1 2 3 4 5 8 7 6 9 10
이어서 수행:
왼쪽 -> 오른쪽 비교와 오른쪽 -> 왼쪽의 비교가 엇갈린다. 이 때에는 엇갈린 위치에서 작은 숫자와 피벗 값의 자리를 교체해 준다.
1 2 3 4 5 6 7 8 9 10
7번째 수행:
왼쪽 연산:
피벗 값 = 6
왼쪽-> 오른쪽(피벗 값 전까지) 연산 했을 때 자신보다 작은 값이 존재하지 않는다. 그러면 자기 자신과 자리를 교체하며 위치가 고정된다.
오른쪽 연산:
피벗 값 = 9
왼쪽-> 오른쪽(피벗 값 전까지) 연산 했을 때 자신보다 작은 값이 존재하지 않는다. 그러면 자기 자신과 자리를 교체하며 위치가 고정된다.
1 2 3 4 5 6 7 8 9 10
8번째 수행:
왼쪽 연산: 7 자기 자신과 자리 교체.
오른쪽 연산: 연산할 게 없다.1 2 3 4 5 6 7 8 9 10
이렇게 피벗 값을 기준으로 왼쪽과 오른쪽을 기준으로 나누어 주는 것. 즉, 작게 쪼개어 작은 단위로 정렬을 한 후 더하는 것이다.(예를 들어 12명이 가위바위보를 하여 승자를 가리면 오래걸리므로, 6명씩 나누어 승자를 정한 후 승자 끼리 다시 가위바위보를 하듯이 나누어 정렬하는 것이다.)
퀵 정렬의 평균 시간 복잡도는 O(N*logN) 이다.
그러나, 피벗 값에 따라서 비효율이 될 수 있다.최악 평균 시간 복잡도는 O(N^2) 이다.
이 것을 코드로 나타내면.
#include <stdio.h>
int num = 10;
int arr[10] = {3, 10, 5, 4, 1, 2, 9, 6, 7, 8};
void quick_sort(int *arr, int start, int end) {
if (start > end) { // 원소가 1개일 때(자기 자리일 때)
return;
}
int pivot = start;
int i = start + 1; // 피벗 왼쪽->오른쪽 시작 값
int j = end; // 오른쪽 -> 왼쪽 시작 값
int temp;
while (i <= j) { // 엇갈릴 때 까지 반복
while (arr[i] <= arr[pivot]) {
i++; // 왼쪽-> 오른쪽 진행
}
while (arr[j] >= arr[pivot] && j > start) {
j--; // 오른쪽 -> 왼쪽 진행
}
if (i >= j) { // 엇갈린 상태면 피벗 값과 교체
temp = arr[j];
arr[j] = arr[pivot];
arr[pivot] = temp;
} else { // 아니면 두개를 교체
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
quick_sort(arr, start, j - 1); // 피벗 값 기준 왼쪽에서 퀵 정렬
quick_sort(arr, j + 1, end); // 피벗 값 기준 오른쪽에서 퀵 정렬
}
int main() {
quick_sort(arr, 0, num - 1);
for (int i = 0; i < num; i++) {
printf("%d ", arr[i]); // 각 원소를 새로운 줄에 출력
}
return 0;
}
파이썬 코드
def quick_sort(arr):
if len(arr) <=1
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x<= pivot]
right = [x for x in arr[1: if x> pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
arr = [3, 10, 5, 4, 1, 2, 9, 6, 7, 8]
print(quick_sort(arr))
파이썬 라이브러리 사용
arr = [3, 10, 5, 4, 1, 2, 9, 6, 7, 8]
arr.sort()
print(arr)