Prosto
퀵 정렬(Quick Sort) - C언어/자료구조 본문
'빠르게 정렬하는 방법으로 가장 많이 사용되는 퀵정렬'
퀵 정렬은 빠른 정렬이나 퀵 소트(Quick Sort)라고도 부릅니다.
퀵 정렬(Qucik Sort)는 데이터를 정렬하는 방법 중 하나입니다.
데이터를 분할(Divide)하고 분할된 부분 별로 이동하는 정복(Conquer) 과정을 반복하여 거쳐 정렬하는 방법입니다.
(지금까지의 정렬들과 달리 조금은 복잡합니다만 보고, 직접 해보며 이해할 수 있을 겁니다.)
성능을 Big O로 표기한다면
average, best = O(n log n)이고, worst = O(n^2)입니다.
일반적으로는 O(n log n)의 성능을 내주지만,
피봇(중심점이) 항상 최솟값이나 최댓값으로 잡힌다면 최악의 성능인 O(n^2)이 나옵니다.
참고로 지금까지 했던 (선택, 삽입, 버블)정렬들은 일반적으로 O(n^2)의 성능입니다.
위의 정렬들과 비교하면 비교적 빠르지만, 최악의 경우는 똑같으 성능을 냅니다.
그렇기 때문에 일반적으로 퀵소트를 사용할 땐 피봇 선택에 대한 예외 처리를 더 해주고 사용합니다.
퀵 정렬(Quick Sort)을 할 때는
분할(Divide), 정복(Conquer)의 용어와
피봇(Pivot), L, R이 무엇인지 이해하고 있어야 합니다.
하나씩 정리를 먼저 해볼까요?
분할(Divide) : 정렬할 자료들을 기준 값(Pivot)을 중심으로 좌, 우 2개의 부분집합으로 나누는 것을 말합니다.
정복(Conquer) : 부분집합의 원소들 중에서 기준 값보다 작은 원소들은 외쪽, 큰 원소들은 오른쪽 부분집합으로 정렬하는 과정입니다.
부분집합의 크기가 더 이상 나눌 수 없을 때까지(부분집합의 원소가 1개 이하) 분할, 정복 과정이 반복됩니다.
피봇(Pivot) : 기준 값 (일반적으로 전체 원소 중 가운데에 위치한 원소)
L : 왼쪽에서 오른쪽으로 움직이며 피봇 이상인 원소를 찾아 L로 지정.
R : 오른쪽에서 왼쪽으로 움직이며 피봇보다 작은 원소를 찾아 R로 지정.
(R은 L과 만나면 더 이상 왼쪽으로 이동하지 않음.)
이걸 기준으로 아래의 데이터를 정렬하는 과정의 그림을 보시면 됩니다.
이렇게 8개의 데이터(배열)을 가지고 퀵 정렬(Quick Sort)를 진행해보겠습니다.
가장 먼저 L을 가장 왼쪽인 12, R을 가장 오른쪽인 6을 가리키고,
Pivot(피봇)은 가운데인 2를 가리킵니다.
(0+7)/2 = 3.5(정수 3)이니 3번째 배열입니다.
(배열 번호는 0 1 2 3 4 5 6 7 .. 순으로 보시면 됩니다.)
L은 12로 Pivot(2) 이상이기 때문에 그대로지만,
R은 Pivot(2)보다 작은 값을 못 찾아 R까지 왔죠?
그러면 L과 Pivot의 값이 서로 바뀌고,
Pivot(2)은 옮겨진 위치 그대로 완료됩니다.
(값 = 2, 위치 = 0)
그리고 Pivot인 2 기준으로 왼쪽 집합 정렬을 시도하지만,
왼쪽은 공집합으로 정렬 대상이 없기 때문에 정렬하지 않고,
Pivot의 우측 집합(9 3 12 7 5 10 6)을 대상으로 퀵 정렬을 시작합니다.
이번엔 가장 왼쪽 L이 9, 가장 오른쪽 R이 6이겠죠?
그리고 중심 값인 Pivot은
(1+7)/2 = 4번째입니다. (Pivot의 값은 7)
(마찬가지로 배열 번호니 다섯 번째죠)
바로 L(9)은 Pivot(7) 이상이고, R(6)은 7 미만이네요.
바로 서로 교환해주고 또 진행합니다.
L은 아까와 마찬가지로 7 이상의 값을 찾아가다가 12에서 멈췄고,
R은 7보다 작은 값을 찾아가다가 5에서 멈췄습니다.
그대로 둘의 값을 바꿔줍니다.
그리고 한 칸씩 또 전진했더니
L은 7 이상의 값인 Pivot(7)을 만나 멈추고,
R은 7 미만의 값은 아니지만 L과 같은 위치니 멈춥니다.
(실제로 소스에서는 약간 다르게 사용하지만, 이렇게 설명하는 게 맞는 것 같습니다.)
그렇게 현재 Pivot인 7의 위치가 확정되었습니다.
다음으로 Pivot이었던 7 기준으로 왼쪽 집합(6 3 5)을 퀵 정렬 합니다.
지금까지와 같이 L, R, Pivot이 설정되었죠?
Pivot은 다시 쓰지만,
(1번째+3번째)/2 = 2번째로 선택된 겁니다.
(0 -> 1 -> 2번째니 값은 3)
L은 3이상이지만,
R은 3 미만 숫자가 없어
5 -> 3을 거쳐 L(6)과 만났습니다.
L과 R이 만났으니 Pivot과 교환합니다.
(현재 상태와 같이 L(피봇보다 큰 값)은 값을 찾았지만,
R은 못 찾고 L(피봇보다 큰 값)까지 갔다는 것은
L로 이동하는 동안 피봇보다 작은 숫자는 없었다(현재 집합의 가장 작은 숫자가 Pivot이다)는
이야기가 되어 L과 Pivot을 바꿔준 겁니다.(L은 Pivot보다 크니 우측으로 가는 것도 맞죠.) )
(피봇 기준 우측에서 이 상황이 벌어졌다면 반대 의미로 똑같이 해석되겠죠.)
이번에도 왼쪽은 공집합이니 진행할 필요가 없고,
우측은 2개의 원소가 있으니 퀵 정렬을 진행해야겠죠?
2번째(6)가 L, 3번째(5)가 R이 되었고,
Pivot으로는 2번째(6)가 되었습니다.( (2+3)/2 = 2 )
L은 피봇(6) 이상, R은 피봇(6) 미만이죠.
조건 만족하니 교환해줍니다.
확정된 왼쪽 집합의 원소가 하나 밖에 없고,
우측은 공집합이기 때문에 더 이상 진행할 수 없습니다.
(현재 왼쪽 부분은 완전히 정렬이 됐죠?)
그리고 아까 7기준으로 왼쪽으로 갔었는데,
이번에는 오른쪽 집합을 이어서 정렬합니다.
L(12)은 Pivot(10) 이상이고, R(9)는 Pivot(10) 미만이니 교환해줍니다.
마지막으로 Pivot과 L R이 만났습니다. 끝이겠죠?
이렇게 퀵 정렬(Quick Sort)를 배열로 살펴봤습니다.
지금 여기서 L은 이상, R은 미만을 기준으로 처리했지만,
L이 초과, R이 이하여도 퀵 정렬 처리가 되겠죠?
(결과적으로 소스 범위 지정이 조금 바뀌겠지만요.)
이제 실제 C언어로 만들어볼까요?
그럼 이번에는 C 언어를 사용하여 퀵 정렬을 해볼까요?
(퀵 정렬은 직접 구현해보면 좋겠지만,
직접 구현하지 못 해도 소스를 보고 이해한다면 충분할 것 같습니다.
필요할 때 알고리즘을 참고하여 만들어도 좋을 테니까요.)
출력 결과 예를 보고
프로그램의 소스를 작성해보세요.
(출력 결과 예1)
단순히 정렬 전, 후만 출력한 결과입니다.
이렇게 보면 어떤 단계에 걸쳐 정렬이 됐는지 잘 모르겠죠.
(출력 결과 예2 - 어떻게 동작하는지 확인하는 의미에서 출력 부분을 추가했습니다.)
그럼 소스를 확인해볼까요?
(참고로, 소스는 위 내용 설명 부분과 차이가 약간 있지만,
Quick Sort로 정렬하는 로직은 동일합니다.)
[퀵 정렬 하는 방식에 약간 차이가 있지만요.
위에서 그림으로 대략적인 구조를 이해했다면
소스로 확실하게 어떻게 작동하는지 확인하셨으면 좋겠네요.]
이미지로 보기엔 한계가 있겠죠?
(이해에 도움이 되도록 주석도 많이 달아뒀습니다.)
복사 가능한 소스로 보도록 합시다.
(실제 실행도 해보고 확인해보세요. main부터 차근차근 따라가며 보셔야겠죠?)
Source.c
#include<stdio.h>
//Prosto
void QuickSort(int arr[], int left, int right) {
int L = left, R = right;
int temp;
int pivot = arr[(left + right) / 2]; //피봇 위치(중앙)의 값을 받음.
printf("L : %d / pivot : %d / R : %d\n", L, (left + right)/2, R); //데이터 확인 부분.
//아래의 while문을 통하여 pivot 기준으로 좌, 우 크고 작은 값 나열. = Partition
while (L <= R) {
//pivot이 중간 값이고, 비교 대상 arr[L], arr[R]은 pivot과 비교하니 중간 지점을 넘어가면 종료로 볼 수 있음.
while (arr[L] < pivot) //left부터 증가하며 pivot 이상의 값을 찾음.
L++;
while (arr[R] > pivot) //right부터 감소하며 pivot 이하 값을 찾음.
R--;
//L, R 모두 최대 pivot 위치까지 이동.
if (L <= R) { //현재 L이 R이하면. (이유 : L>R 부분은 이미 정리가 된 상태임).
if (L != R) { //같지 않은 경우만.
temp = arr[L];
arr[L] = arr[R];
arr[R] = temp;
} //L과 R이 같다면 교환(SWAP)은 필요 없고 한 칸씩 진행만 해주면 됨.
L++; R--; //그리고 L,R 한 칸 더 진행.
for (int i = 0; i < 10; i++) { //데이터 확인 부분.
printf("%d ", arr[i]);
}
printf("\n");
}
}
printf("\n");
//조건 확인하여 재귀함수로.
printf("QuickSort 재귀 호출 확인(만족 시 호출)\n1.left : %d < R : %d \n2.right : %d > L : %d\n\n", left, R, right, L); //데이터 확인 부분.
if (left < R)
QuickSort(arr, left, R);
if (L < right)
QuickSort(arr, L, right);
}
int main(void) {
//int data[10] = { 10, 6, 7, 9, 3, 4, 2, 1, 5, 8 };
//int data[10] = { 10, 6, 7, 2, 9, 1, 8, 3, 5, 4 };
//int data[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int data[10] = { 2, 9, 4, 18, 5, 1, 7, 8, 15, 12 };
//랜덤한 위치라고 생각.
printf(" --정렬 전 순서--\n"); //정렬하기 전 상태 출력.
for (int i = 0; i < 10; i++) {
printf("%d ", data[i]);
}
printf("\n\n");
QuickSort(data, 0, 9); // 9 = 10-1
printf(" --정렬 후 순서--\n"); //정렬한 후 상태 출력.
for (int i = 0; i < 10; i++) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
(소스 수정했습니다.)
퀵 정렬 이해에 도움이 됐나요?
(추가로 메일로 오류 부분 지적해주신 '우동혁'님 감사합니다. [요즘 정신이 없어 수정하는데 오래걸렸네요...] )
궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )
'Programing > C Programing' 카테고리의 다른 글
| 재귀적 호출(순환 호출) 함수의 이해와 예제, 문제 -C언어 (4) | 2016.11.11 |
|---|---|
| 사용자 정의 함수의 이해와 예제, 문제 -C언어 (7) | 2016.11.05 |
| 이분 검색(Binary Search) - C언어/자료구조 (6) | 2016.10.20 |
| 삽입 정렬(Insertion Sort) - C언어/자료구조 (5) | 2016.10.19 |
| 버블 정렬(Bubble Sort) - C언어/자료구조 (4) | 2016.10.18 |
