이번에는 퀵 정렬 알고리즘을 구현해 보기로 해요.
퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)
조건(n<=1)
종료
피벗을 선택한다.
피벗과 맨 앞의 요소를 교환한다.
big:=0
small:=n
반복(big<small)
반복(big:=big+1; big<n; big:=big+1)
조건(compare(base[0],base[big])<0)
루프 탈출
반복(small:small-1;small>0;small:small-1)
조건(compare(base[0],base[small])>0)
루프 탈출
조건(big<small)
교환(base [big], base [small])
교환(base [0], base [small])
퀵 정렬(base,small, compare)
퀵 정렬(base+big, n-big, compare)
참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.
template <typename data, typename compare>
//퀵 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
void quick_sort(data *base, size_t n, compare com)
{
퀵 정렬의 탈출 조건은 정렬할 원소 개수가 1보다 작거나 같을 때입니다.
if(n<=1) //조건(n<=1)
{
return; //종료
}
피벗을 선택합시다. 여기에서는 맨 앞, 중간, 마지막 원소 중에 중간 값을 갖는 원소를 피벗으로 선택할 것입니다.
//피벗 선택
int pivot = 0; //피벗의 위치를 기억하기 위한 변수
//먼저 맨 앞과 맨 마지막 원소를 비교합시다.
if(com(base[0],base[n-1])>0)
{
//맨 앞의 원소가 마지막 원소보다 큰 것은 알았습니다.
//다시 맨 앞과 중간에 있는 원소를 비교합시다.
if(com(base[0],base[n/2])>0)
//base[0]이 제일 큰 값, 이 조건인 거짓일 때는 0번째 원소가 중간 값
{
//맨 앞의 원소가 마지막 원소와 중간에 있는 원소보다 큰 것을 알았습니다.
//이제 맨 앞과 중간에 있는 원소 중에 큰 값이 피벗입니다.
if(com(base[n/2],base[n-1])>0) //둘 중에 큰 값이 중간 값
{
//중간에 있는 원소가 더 크므로 중간 값은 중간에 있는 원소입니다.
pivot = n/2;
}
else
{
//맨 뒤에 있는 원소가 더 크므로 중간 값은 맨 뒤에 있는 원소입니다.
pivot = n-1;
}
}
}
else //base[n-1]이 base[0]보다 크거나 같음
{
//맨 앞의 원소가 마지막 원소보다 크지 않습니다.
//중간에 있는 원소와 마지막 원소를 비교하세요.
if(com(base[n/2],base[n-1])>0)
{
//중간에 있는 원소가 크므로 맨 뒤에 있는 원소가 중간 값입니다.
pivot = n-1; //n-1번째 원소가 중간 값
}
else//n-1번째 원소가 제일 큰 값
{
//맨 뒤에 원소가 맨 앞 원소와 중간에 있는 원소보다 작지 않다는 것을 알았습니다.
//중간에 있는 원소와 맨 앞의 원소를 비교하세요.
if(com(base[n/2],base[0])>0)//이 조건인 거짓일 때는 0번째 원소가 중간 값
{
//중간에 있는 원소가 맨 앞의 원소보다 크므로 중간 값은 중간에 있는 원소입니다.
pivot = n/2;//n/2가 중간 값
}
}
}
피벗을 선택하였으면 맨 앞의 원소와 피벗에 있는 요소를 교환하세요.
swap(base[0],base[pivot]);//피벗과 맨 앞의 요소 교환
이제 피벗을 중심으로 큰 값은 왼쪽으로 작은 값들은 오른쪽으로 배치할 것입니다. 이를 위해 앞에서부터 피벗보다 큰 값을 찾고 뒤에서부터 피벗보다 작은 값을 찾는 과정을 반복할 것입니다. 만약 큰 값이 작은 값보다 앞에 있으면 둘을 교환하는 것을 반복할 거예요.
size_t big=0, small=n; //피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수
while(big<small)//반복(big<small)
{
//순차적으로 피벗과 비교하면서 더 큰 값을 만나면 반복문을 탈출하세요.
for(big++; big<n; big++)//반복(big:=big+1; big<n; big:=big+1)
{
if(com(base[0],base[big])<0)//조건(compare(base[0],base[big])<0)
{
break;//루프 탈출
}
}
//역순으로 피벗과 비교하면서 더 작은 값을 만나면 반복문을 탈출하세요.
for(small--; small>0; small--)//반복(small:small-1;small>0;small:small-1)
{
if(com(base[0],base[small])>0)//조건(compare(base[0],base[small])>0)
{
break;//루프 탈출
}
}
//큰 값이 있는 위치가 작은 값이 있는 위치보다 앞이면 둘은 교환하세요.
if(big<small)//조건(big<small)
{
swap(base[big],base[small]); //교환(base [big], base [small])
}
}
이제 피벗을 중심으로 작은 값들은 왼쪽에 큰 값은 오른쪽에 배치하였습니다. 작은 값들 중에 맨 뒤에 있는 요소와 피벗을 교환하세요.
swap(base[0],base[small]);//교환(base [0], base [small])
재귀함수로 피벗보다 작은 값들이 있는 배열을 정렬합니다.
quick_sort(base,small,com);//퀵 정렬(base,small, compare)
재귀함수로 피벗보다 큰 값들이 있는 배열을 정렬합니다.
quick_sort(base+big,n-big,com);//퀵 정렬(base+big, n-big, compare) }
테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 quick_sort로 변경하세요.
#define MAX_DATA 1000
int main()
{
Member *base[MAX_DATA];
//퀵 정렬이 잘 동작하는지 10개 원소를
//번호 순으로 정렬하여 확인하고
//이름 순으로 정렬하여 확인하세요.
MakeRandomMembers(base,10);
cout<<"정렬 전"<<endl;
ViewMembers(base,10);
quick_sort(base,10,CompareByNum);
cout<<"번호로 정렬 후"<<endl;
ViewMembers(base,10);
quick_sort(base,10,CompareByName);
cout<<"이름으로 정렬 후"<<endl;
ViewMembers(base,10);
RemoveMembers(base,10);
//그리고 MAX_DATA 개일 때 수행 속도와
//MAX_DATA/10 개일 때 수행 속도를 비교해 보세요.
clock_t st,et;
MakeRandomMembers(base,MAX_DATA);
cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
st = clock();
quick_sort(base,MAX_DATA,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA);
MakeRandomMembers(base,MAX_DATA/10);
cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
st = clock();
MakeRandomMembers(base,MAX_DATA/10);
quick_sort(base,MAX_DATA/10,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA/10);
return 0;
}
다음은 실행 결과예요.
▷실행 결과
정렬 전 0000757147,이름0167851000 0301413356,이름0336971124 0659598368,이름0160567225 0391749387,이름0004890851 0035766290,이름0026239572 0473038164,이름0000597006 0003615544,이름0326051436 0392289610,이름0118341522 0170427798,이름0037215528 0675016433,이름0168544290 번호로 정렬 후 0000757147,이름0167851000 0003615544,이름0326051436 0035766290,이름0026239572 0170427798,이름0037215528 0301413356,이름0336971124 0391749387,이름0004890851 0392289610,이름0118341522 0473038164,이름0000597006 0659598368,이름0160567225 0675016433,이름0168544290 이름으로 정렬 후 0473038164,이름0000597006 0391749387,이름0004890851 0035766290,이름0026239572 0170427798,이름0037215528 0392289610,이름0118341522 0659598368,이름0160567225 0000757147,이름0167851000 0675016433,이름0168544290 0003615544,이름0326051436 0301413356,이름0336971124 수행 성능 테스트1 자료 개수:1000 수행 속도:79 수행 성능 테스트2 자료 개수:100 수행 속도:6
퀵 정렬의 결과를 보면 자료 개수가 MAX_DATA일 때 MAX_DATA/10일 때보다 130배 정도 느린 것을 알 수 있습니다. 앞에서 알고리즘 성능을 분석할 때 O(nlogn)과 비슷하죠. 이제까지 구현했던 순차, 거품, 선택, 삽입 정렬 알고리즘보다 수행 성능이 뛰어난 것을 알 수 있습니다.