Quick Sort
시간복잡도 : O(Nlog_2N) 이지만 최악의 경우는 마찬가지로 O(N^2)
퀵 정렬은 아주 빠른 속도를 나타낼뿐만 아니라 원리도 간단해서 많은 응용 분야에서 사용되고 있다.
퀵 정렬은 연속적인 분할에 의해서 정렬한다.
축(Pivot)값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값을 배열시키는 것이다.
이렇게 하여 축값의 왼쪽과 오른쪽 부분을 각각 또다시 분할하고 하는 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.
-리스트 마지막 인덱스의 값을 pivot으로 정함.
피봇을 뺀 나머지 배열에서 가장 양쪽 끝 인덱스를 저장. 왼쪽은 i, 오른쪽은 j (인덱스 2개 사용)
i는 오른쪽으로 가면서 해당 값이 pivot보다 작아야 한다. 큰 것이 발견되면 멈춤.
j는 왼쪽으로 가면서 해당 값이 pivot보다 커야 한다. 작은 것이 발견되면 멈춤.
i위치와 j위치의 값을 바꿈.
그런데, i, j가 만나게 되는 경우. (i>=j) 해당 위치가 pivot이 들어갈 자리.
i위치의 값과 pivot 값 swap한다.
pivot을 기준으로 왼쪽, 오른쪽으로 리스트를 나누어, 각각 처음부터 다시 소팅한다.
알고리즘
- 만약 n>1 이면
- 1 N 크기의 a 배열을 분할 하여 축값의 위치를 mid로 넘긴다.
- 2 퀵 정렬 알고리즘(a, mid)
- 3 퀵 정렬 알고리즘 (a+mid-1, N-mid-1)
void quick_sort(int a[], int n){
int v, t;
int i, j;
if (n > 1){
v = a[n - 1]; // v=축값. 마지막 노드값을 사용
i = -1;
j = n - 1;
while (1){ // 분할
while (a[++i] < v); // 왼쪽에서부터 축값보다 크거나 같은 값이 있는지?
while (a[--j] > v){ // 오른쪽에서부터 축값보다 작거나 같은 값이 있는지? -> 가장작은값이 pivot이면?? index out range 위험 아래 체크 필요.
if (j==0) break ;
}
if (i >= j) break; // i와 j의 위치가 뒤바뀌었으면 분할 끝
t = a[i]; // 아니면 두 값을 바꿈
a[i] = a[j];
a[j] = t;
}
t = a[i]; // 축 값과 축값의 위치에 있는 값을 바꿈
a[i] = a[n - 1];
a[n - 1] = t;
quick_sort(a, i); // 왼쪽 구간 퀵정렬
quick_sort(a + i + 1, n - i - 1); // 오른쪽 구간 퀵정렬
}
}
퀵 정렬은 난수 배열이나 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 엄청나게 떨어진다.
퀵 정렬의 이상적인 경우는 분할이 정확하게 구간을 양분하는 것이다. 이 경우 재귀의 깊이는 logN이 되며 가장 빠른 속도를 나타낸다.
이렇게 퀵 정렬은 분할할 축값이 어느 정도 그 구간의 중앙을 나누느냐에 성능이 좌우된다.
재귀 호출로 인해서 내부 스택이 사용된다. 따라서 퀵 정렬이 속도가 빠른 반면에 메모리의 희생이 있다.
N이 커지면 커질수록 스택의 크기가 커지며 스택 오버플로우가 발생할 수 있다.
성능개선: 이미 정렬된 상태인지를 체크하는 것을 추가한다.
ex)
0,1,2,3,4,5,6,7,8 : 인덱스
5,3,8,4,9,1,6,2,7 : 값
qsort
- 피봇을 마지막 번째 노드 값으로 정하자. (보통 첫번째나 마지막번째로 정함.)
남은 데이터의 양쪽 끝에서 가운데로 스캔해 나가면서 왼쪽에서는 피봇보다 큰 값을 찾으면 멈추고, 오른쪽에서는 피봇보다 작은 값을 찾으면 멈추고, 둘을 교환한다.
pivot=7, scan index=0, 7 start find over or below than pivot.
stop index=2(큰값발견),7(작은값발견) value 8>7>2 ;swap
0,1,2,3,4,5,6,7,8
5,3,2,4,9,1,6,8,7
pivot=7, stop index=4, 6 value 9>7>6 ;swap
0,1,2,3,4,5,6,7,8
5,3,2,4,6,1,9,8,7
pivot=7, stop index=6> 5 ; cross
stop. index=5, 4 인덱스가 교차되면 멈추고, 피봇(오른쪽 파트위치로 인덱스를 잡았으므로 right part에 속해야 한다. left part의 마지막 스캔 위치 인덱스6, 피봇보다 큰 수를 처음 발견한 지점에 들어가야 한다. )과 left last index(6)와 swap
0,1,2,3,4,5,6,7,8
5,3,2,4,6,1,7,8,9
피봇을 기준으로 좌우 분리가 끝남.
피봇 위치가 바뀌면 한 싸이클이 끝난 것임. (pivot 7을 기준으로 좌(low)우(high) 분리 완료)
- 좌우 파트("532461", "89")에 대해 각각 qsort 수행. 파트의 원소 개수가 1이면 스킵.
2-2.
0 1 (실제 인덱스는 7,8)
8 9
pivot=9, stop=N, 0. 왼쪽값을 찾지 못함. 즉, 모두 작다. 이미 피봇은 가장 우측이라 변경할 필요가 없다. 리턴
2-1.
0,1,2,3,4,5
5,3,2,4,6,1
new pivot=1, start 0, 4
pivot=1, stop 0, N; 왼쪽에서는 큰 값을 찾았는데, 오른쪽에서는 작은 값을 찾지 못함. left part last index=0과 swap
0,1,2,3,4,5
1,3,2,4,6,5
좌우 파트 수행 : "", "32465". 왼쪽 파트는 1개이하라 스킵. 오른쪽 파트 수행
0 1 2 3 4 (실제 인덱스 : 1,2,3,4,5)
3 2 4 6 5
new pivot=5 ; start 0, 3
pivot=5, stop=3>2.cross! last left index=3. change
0 1 2 3 4 (실제 인덱스 : 1,2,3,4,5)
3 2 4 5 6
좌우 파트 수행 : "3 2 4", "6" ; 오른쪽 파트는 스킵.
0 1 2 (실제 인덱스 : 1,2,3)
3 2 4
pivot=4, stop=N, 1 no swap. break
좌우 파트 수행 "32", ""
0 1 (실제 인덱스 : 1,2)
3 2
pivot=2, start=0,0
pivot=2, stop=0, N ; swap with index 0
0 1 (실제 인덱스 : 1,2)
2 3
6. 좌우 분할 ; "", "3" ; 모두 리턴
0,1,2,3,4,5,6,7,8 : 인덱스
1,2,3,4,5,6,7,8,9 : 값
vector<double> QuickSort(vector<double>& vec1){
double i = 0;
double j = vec1.size()-2;
double tmp;
int pivotindex = vec1.size()-1 ;
double pivot = vec1[pivotindex];
if ( vec1.size()<=1 )
return vec1 ;
cout << "QuickSort: ";
printvector(vec1) ;
while (i <= j) {
while (vec1[i] < pivot)
i++;
while (vec1[j] > pivot)
j--;
if (i <= j) {
tmp = vec1[i];
vec1[i] = vec1[j];
vec1[j] = tmp;
i++;
j--;
}
}
// pivot change
vec1[pivotindex] = vec1[i] ;
vec1[i]=pivot ;
pivotindex=i ;
cout << "pivotting: ";
printvector(vec1) ;
if (vec1.size()<=2 )
return vec1 ;
// partition
vector<double> left_vec, right_vec ;
vector<double>::iterator pivotiter = vec1.begin()+pivotindex ;
copy(vec1.begin(), pivotiter, back_inserter(left_vec)) ;
copy(pivotiter+1, vec1.end(), back_inserter(right_vec)) ;
cout << "left: ";
printvector(left_vec) ;
cout << "right: ";
printvector(right_vec) ;
if (left_vec.size()>0 ) {
QuickSort(left_vec);
copy(left_vec.begin(), left_vec.end(), vec1.begin()) ;
}
if (right_vec.size()>0 ) {
QuickSort(right_vec);
copy(right_vec.begin(), right_vec.end(), pivotiter+1) ;
}
return vec1;
}
