3.3.2 퀵 정렬 알고리즘 구현
퀵 정렬 알고리즘.zip2 장에서 만들었던 정렬 알고리즘과 같은 방법으로 시뮬레이션 코드를 작성합니다. 여기에서는 퀵 정렬 알고리즘만 구현할게요. 참고로 퀵 정렬 알고리즘을 내부 알고리즘을 별도의 함수로 구현하지 않고 직접 구현할게요. 정렬 알고리즘은 수행 속도가 중요한 이슈이므로 복잡하더라도 하나의 함수로 구현할게요.
void quick_sort(Element *base, int n, Compare compare)
{
먼저 교환에 사용할 임시 변수와 피벗의 위치와 피벗보다 큰 값과 작은 값의 위치를 기억하기 위한 변수를 선언합시다.
Element temp;//교환을 위한 임시 변수
int pivot = 0; //피벗의 위치를 기억하기 위한 변수
int big=0, small=0; //피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수
만약 원소의 개수가 1보다 작거나 같으면 함수를 종료합니다. 이 부분이 재귀 함수의 탈출 조건입니다.
if(n<=1)
{
return;
}// 조건(n<=1) 종료
피벗을 선택합니다. 여기에서는 맨 앞의 원소와 중간에 있는 원소, 맨 뒤에 있는 원소 중에 중간 값을 피벗으로 선택할게요. 먼저 맨 앞의 원소와 맨 뒤의 원소를 비교합시다.
if(compare(base[0],base[n-1])>0)
{
만약 맨 앞의 원소가 크면 중간에 있는 원소와 다시 비교합니다.
if(compare(base[0],base[n/2])>0) //base[0]이 제일 큰 값, 이 조건인 거짓일 때는 0번째 원소가 중간 값
{
이 때도 맨 앞의 원소가 크면 일단 제일 큰 값은 맨 앞에 있는 원소입니다. 이 때는 중간에 있는 원소와 맨 뒤에 있는 원소를 비교해야 중간 값을 알 수 있습니다. 이 둘을 비교하여 큰 값이 중간 값입니다.
if(compare(base[n/2],base[n-1])>0) //둘 중에 큰 값이 중간 값
{
pivot = n/2;
}
else
{
pivot = n-1;
}
}
}
만약 n-1번째 원소가 0번째 원소보다 크거나 같을 때의 피벗을 찾아봅시다.
else //base[n-1]이 base[0]보다 크거나 같음
{
중간에 있는 원소와 맨 뒤의 원소를 비교하여 중간에 있는 원소가 더 크면 맨 뒤의 원소가 중간 값입니다.
if(compare(base[n/2],base[n-1])>0)
{
pivot = n-1; //n-1번째 원소가 중간 값
}
그렇지 않다면 맨 뒤에 있는 원소가 제일 큰 값입니다.
else//n-1번째 원소가 제일 큰 값
{
이 때는 다시 중간에 있는 원소와 맨 앞의 원소를 비교합니다. 이 둘 중에 큰 값이 중간 값입니다.
if(compare(base[n/2],base[0])>0)//이 조건인 거짓일 때는 0번째 원소가 중간 값
{
pivot = n/2;//n/2가 중간 값
}
}
}
이제 피벗과 맨 앞의 요소를 교환합니다.
//피벗과 맨 앞의 요소를 교환한다.
temp = base[pivot];
base[pivot] = base[0];
base[0] = temp;
앞쪽부터 피벗보다 큰 값이 있는지 확인할 것입니다. 그리고 뒤쪽부터 작은 값이 있는지 확인할 것입니다. big을 0으로 초기화하고 small을 n으로 초기화하는 이유는 이전에 찾은 위치 다음으로 이동한 후에 찾는 작업을 할 것이기 때문입니다.
big=0;//big:=0
small = n;//small:=n
피벗보다 큰 값을 발견한 위치가 작은 값을 발견한 위치보다 앞이면 아직 피벗을 기준으로 작은 값들과 큰 값들을 배치하는 작업을 계속 해야 합니다.
while(big<small)//반복(big<small)
{
먼저 피벗보다 큰 값을 찾습니다. 이전에 위치 뒤로 이동한 후에 마지막 요소까지 순차적으로 이동하면서 찾습니다.
for(big++; big<n; big++)// 반복(big:=big+1; big<n; big:=big+1)
{
만약 피벗보다 big위치의 원소가 더 크면 루프를 탈출합니다.
if(compare(base[0],base[big])<0)// 조건(compare(base[0],base[big])<0)
{
break;// 루프 탈출
}
}
피벗보다 작은 값을 찾습니다. 이전에 위치 앞으로 이동한 후에 맨 앞까지 순차적으로 이동하면서 찾습니다. 그리고 피벗보다 small 위치의 원소가 더 작으면 루프를 탈출합니다.
for(small--; small>0; small--)// 반복(small:small-1;small>0;small:small-1)
{
if(compare(base[0],base[small])>0)// 조건(compare(base[0],base[small])>0)
{
break;// 루프 탈출
}
}
만약 big 위치가 small 위치보다 앞이면 두 원소를 교환합니다.
if(big<small)// 조건(big<small)
{
// 교환(base [big], base [small])
temp = base[big];
base[big] = base[small];
base[small] = temp;
}
}
이제 피벗과 small위치의 원소를 교환합니다. 이를 수행하면 피벗보다 작은 값들은 왼쪽에 존재하고 큰 값들은 오른쪽에 존재하고 피벗은 정렬을 완료한 상태에 있어야 할 위치에 존재합니다.
//교환(base [0], base [small])
temp = base[0];
base[0] = base[small];
base[small] = temp;
피벗보다 앞쪽을 재귀함수로 정렬합니다. 그리고 뒤쪽도 재귀함수로 정렬합니다.
quick_sort(base,small,compare);//퀵 정렬(base,small, compare)
quick_sort(base+big,n-big,compare);//퀵 정렬(base+big, n-big, compare)
}
재귀 함수의 깊이가 깊어지면 스택 메모리가 부족할 수 있습니다. 필요하면 프로젝트 속성 창을 열어 스택 크기를 설정하세요.
[그림 3.5] 프로젝트 스택 크기 설정
테스트를 해 보면 자료 개수가 10배 늘었을 때 20배 정도의 속도 차이가 나는 것을 알 수 있습니다. 하지만 피벗을 선택하여 맨 앞의 원소와 교환하는 부분을 주석 처리하고 정렬 상태의 배열이나 역순으로 정렬 상태의 배열을 정렬 요청하면 최악의 속도가 나오는 것을 확인할 수 있습니다.
[그림 3.6] 퀵정렬의 수행 속도 비교 화면
'언어 자료구조 알고리즘 > [C]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| [디딤돌 자료구조와 알고리즘 with C] 4.3 병합 정렬 알고리즘 (0) | 2016.04.10 |
|---|---|
| [디딤돌 자료구조와 알고리즘 with C] 4.2 이진 탐색 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 4. 분할 정복 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3.4.2 이진 탐색 트리 코드 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3.4 이진 탐색 트리 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3.3 퀵 정렬 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3.2 하노이 타워 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3. 재귀 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 2.4.2 삽입 정렬 알고리즘 구현 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 2.4 삽입 정렬 알고리즘 (2) | 2016.04.10 |