안녕하세요 기린입니다 :)
지난 시간까지 다루었던 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘 모두 시간 복잡도 O(N^2)를 가지는 알고리즘 이었는데요.
이러한 알고리즘 들은 데이터의 갯수가 10만 개만 넘어가도 사용하기가 매우 어려운 알고리즘입니다.
그렇기 때문에 더욱 빠른 정렬 알고리즘이 필요하겠죠 ?
자 대표적으로 빠른 알고리즘인 퀵 정렬에 대해 알아보겠습니다.
퀵 정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN) 입니다. 예시를 통해 바로 확인해보시죠 :]
다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 10 5 8 7 6 4 3 2 9
퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 방법으로 빠르게 정렬하는데요, 더 쉽게 말해 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다.
바로 한 번 살펴보도록 하죠 !
일반적으로 퀵 정렬에서는 기준 값이 있는데 이를 피벗(Pivot)이라 합니다. 보통 첫 번째 원소를 피벗 값으로 설정하고 사용하는데요. 다음과 같이 1이라는 값이 먼저 피벗 값으로 설정되었다 생각해봅시다.
(1) 10 5 8 7 6 4 3 2 9
-> 10
1 <-
이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾습니다. 이 때 1보다 큰 숫자로 10, 작은 숫자는 찾지 못해 1 까지 도달하게 됩니다. 이 때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 피벗 값과 작은 값의 위치를 변경합니다. 즉, 1과 1을 교환하므로 정렬에 변함이 없겠죠 !
위와 같은 방법으로 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 수행하면 되는데요
1 (10) 5 8 7 6 4 3 2 9
-> 10
9 <-
자 이제 피벗값 기준으로 왼쪽은 없으므로 무시하고, 오른쪽 피벗값으로 10이 채택됩니다. 그리고 10보다 큰 값을 왼쪽부터, 10보다 작은 값을 오른쪽부터 찾습니다. 큰 값은 찾지 못하게 되며 작은 값으로는 바로 9를 찾을 수 있습니다. 이 때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 9와 10을 교환합니다.
1 9 5 8 7 6 4 3 2 10
따라서 위와 같이 구성이 되며, 이 때 피벗 값이었던 10의 왼쪽에는 10보다 작은 값이 존재하고 오른쪽에는 10보다 큰 값이 존재하게 되는거죠. 이해 되시나요 ???
즉, 한번 수행할때마다 피벗값의 위치를 찾게되는거죠
이렇게 퀵 정렬을 순환적으로 수행하면 반으로 쪼개 들어가면서 분할 정복식으로 정렬이 완료됩니다
이게 왜 빠른지 생각해보겠습니다
예를들어 10자리 수를 정렬할 때 선택 정렬을 기준으로 시간 복잡도가 N^2 = 10 * 10 = 100 이 나오는데요
10자리 수를 반으로 나누어 시간 복잡도를 계산해보면 5 * 5 = 25 와 5 * 5 = 25 로 50이 나온다는거죠
이해 되시나요 ? 이를 전부 1개씩 나누게 되면 1 * 1 를 10번 수행한다고 생각하시면 되겠죠 ??
자 이제 소스코드를 보실게요
#include <stdio.h>
int number = 10;
int data[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
void show() {
int i;
for (i = 0; i < number; i++) {
printf("%d ", data[i]);
}
}
void quickSort(int* data, int start, int end) {
if (start >= end) { // 원소가 1개인 경우 그대로 두기
return;
}
int key = start // 키는 첫 번 째 원소
int i = start + 1, j = end, temp;
while (i <= j) { // 엇갈릴 때까지 반복
while (i <= end && data[i] <= data[key]) { // 키 값보다 큰 값을 만날 경우
i++;
}
while (j > start && data[j] >= data[key]) { // 키 값보다 작은 값을 만날 경우
j--;
}
if (i > j) { // 현재 엇갈린 상태면 키 값과 교체
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else { // 엇갈리지 않았다면 i와 j를 교체
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
quickSort(data, 0, number - 1);
show();
return 0;
}위 소스코드를 보시면 '키 값보다 작은 값을 만날때까지' 반복하는 부분에서 j 가 start 보다 클 때에 한해서만 반복문이 수행되도록 처리되어 있습니다. 이는 항상 왼쪽에 있는 값과 피벗 값을 교환하기 때문인데요 오른쪽에 있는 값은 피벗 값과 교환되지 않으므로 처리해 줄 필요가 없습니다. 즉 퀵 정렬 알고리즘은 기본적으로 N번씩 탐색하되 반으로 쪼개 들어간다는 점에서 logN 을 곱한 복잡도를 가집니다.
하지만 퀵 정렬의 최악 시간 복잡도는 O(N^2) 인데요
다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 2 3 4 5 6 7 8 9 10
위와 같이 이미 정렬이 되어 있는 경우 퀵 정렬의 시간 복잡도 O(N^2)에 가깝습니다. 반면에 이전 시간에 다루었던 삽입 정렬의 경우 위 문제를 매우 빠르게 풀어낼 수 있습니다. 즉 정렬할 데이터의 특성에 따라서 적절한 정렬 알고리즘을 사용하는 것이 중요하다는 것입니다. 자 그럼 위의 문제를 내림차순으로 바꾸어보는 문제를 한번 풀어보길 권장드립니다
자 그럼 즐거운 코딩하세요 !
문의: ralla0405@gmail.com
