▷ 주어진 입력 리스트를 피봇(pivot) 또는 제어키(control key)이라 불리는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음, 이러한 두 개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식
▷ 퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은 입력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠▷ 분할 및 정복 방법 사용
▷ 피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열
▷ 퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할 경우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고, 오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이 수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작은 키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열된 서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.
■ 퀵 정렬 알고리즘 단계 : 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}
■ 특징
▷ 평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
- 실제 수행속도가 가장 빠른 정렬 알고리즘
▷ 스택 공간을 사용
▷ 재귀 호출을 기반으로 동작
■ 예제로 보는 퀵 정렬 단계
ㅇ
■ 퀵 정렬 과정 사례
① 초기 데이터
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
8 |
1 |
4 |
9 |
6 |
3 |
5 |
2 |
7 |
0 |
② 3수의 중위수 피봇
- 왼쪽, 중앙, 오른쪽 세수를 정렬한다.
- 중앙의 수를 피봇한다.
- 피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP한다.
|
0 |
1i |
2 |
3 |
4 |
5 |
6 |
7 j |
8 |
9 |
|
0 |
1 |
4 |
9 |
7 |
3 |
5 |
2 |
6 |
8 |
|
왼쪽 |
중앙 |
피봇 |
오른쪽 |
③ 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
1. i 위치의 수를 피봇수와 비교하면서 증가시킴, 클 때 중단
2. j 위치의 수를 피봇수와 비교하면서 감소시킴, 작을 때 중단
3. i<j이면 i,j의 위치에 있는 수를 SWAP한다.
|
0 |
1 |
2 |
3 i |
4 |
5 |
6 |
7 j |
8 |
9 |
|
0 |
1 |
4 |
2 |
7 |
3 |
5 |
9 |
6 |
8 |
|
왼쪽 |
피봇 |
오른쪽 |
|
0 |
1 |
2 |
3 |
4 i |
5 |
6 j |
7 |
8 |
9 |
|
0 |
1 |
4 |
2 |
5 |
3 |
7 |
9 |
6 |
8 |
|
왼쪽 |
피봇 |
오른쪽 |
i>j이면 피봇 수와 i의 위치에 있는 수를 SWAP한다.
|
0 |
1 |
2 |
3 |
4 |
5 j |
6 i |
7 |
8 |
9 |
|
0 |
1 |
4 |
2 |
5 |
3 |
6 |
9 |
7 |
8 |
|
왼쪽 |
피봇 |
오른쪽 |
④ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 | ||
|
0 |
1 |
4 |
2 |
5 |
3 |
6 |
9 |
7 |
8 | ||
■ 퀵 정렬 알고리즘
|
----------------------------------------------------------------------------- void Quicksort(int A[], int N) {Qsort(A,0, N-1); } /* 퀵 정렬 호출 함수 */ int Median3(int A[], int Left, int Right) /* 세 수의 중위수 계산 함수 */ { int Center= (Left + Right) / 2; /* A[Left]<= A[Center]<= A[Right]*/ lf( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] ); if( A[Left] > A[Right] ) Swap( &A[Left], &A[Right] ); if( A[Center] > A[Right]) Swap(&A[Center], &A[Right]); swap( &A[Center], &A[Right-1] ); /* 피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP */ return A[Right-1]; /*return 피봇 */ } #define Cutoff(3) /* 퀵 정렬 함수 */ void Qsort( int A[], int Left, int Right ) /* 배열 A의 왼쪽 끝 첨자:Left, 오른쪽 끝 첨자:Right */ { int i, j, Pivot; /*1*/ if( Left + Cutoff <= Right ) /*2*/ { Pivot = Median3( A, Left, Right); /*3*/ i=Left; j=Right-1; /*4*/ for( ; ; ) /*5*/ { while( A[++i ] < Pivot ){} /*6*/ while( A[--j ] > Pivot ){} /*7*/ if( i < j ) /*8*/ swap( &A[ i ], &A[ j ] ); /*9*/ else break; } /*10*/ swap( &A[ i ], &A[ Right-1] ); /*11*/ Qsort( A, Left, i-1 ); /*12*/ Qsort( A, i+1, Right ); } else /*13*/ InsertionSort( A+Left , Right-Left+1) } ②세 수의 중위수 계산, Pivot에 중앙값 넣기 ⑤배열의 왼쪽에서부터 중앙값보다 큰 원소까지 이동 ⑥배열의 오른쪽에서부터 원소의 값이 중앙값보다 작은 원소까지 이동 ⑦⑧⑨정렬이 끝나지 않았으면 중앙값보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 들어가도록 교체함. 정렬이 끝났으면 무한루프를 벗어남 ⑩중앙값보다 큰 첫 번째 요소와 중앙값을 교환해 중앙값을 작은 값과 큰 값 사이에 끼워 넣음. 중위치 정렬 ⑪왼쪽부분리스트(중앙값보다 작은부분)의 퀵정렬 ⑫오른쪽부분리스트(중앙값보다 큰부분)의 퀵정렬 ⑬원소가 Cutoff보다 작거나 같은 서브트리의 삽입정렬 ----------------------------------------------------------------------------- |
■ 성능
▷ 최악의 경우: O(n2)
▷ 평균: O(nlogn)
▷ 최선의 경우는 n 개의 데이터가 저장된 배열이 각 분할 단계에서 정확히 이등분 될 때
▷ 교환 및 비교 회수가 매우 적음 : 단순하고 매우 빠른 속도로 수행
▷ 안정성은 없음
▷ 난수 배열 및 반쯤 정렬된 배열 자료에 대해서는 성능이 우수
▷ 피봇이 중간 값을 갖도록 해야 수행속도가 좋아짐
##[퀵소트 다른 내용 보기]
출처 : 한국교원대학교 교육대학원 컴퓨터교육과
