빗 정렬(Comb Sort)의 기본 아이디어는 거품 정렬(Bubble Sort)과 같습니다. 다시 말해, 빗 정렬은 거품 정렬을 개선한 알고리즘입니다. 거품 정렬에서는 각 단계마다 인접한 항목끼리 비교를 수행하지만, 빗 정렬에서는 일정한 간격(gap)을 두고 떨어져 있는 항목들을 비교하며 정렬합니다.
한 단계(phase)가 끝날 때마다 간격은 점차 줄어들며, 이때 사용되는 감소 계수(shrink factor)는 1.3입니다. 즉, 매 단계가 완료될 때마다 현재 간격을 1.3으로 나눈 값으로 갱신합니다. 이러한 방식 덕분에 빗 정렬은 거품 정렬보다 작은 값을 앞쪽으로 더 빠르게 이동시킬 수 있어 성능이 크게 향상됩니다.
빗 정렬 기법의 복잡도
- 시간 복잡도: 최선의 경우 O(n log n), 평균의 경우 O(n^2/2^p)(p는 증분 횟수), 최악의 경우 O(n^2)
- 공간 복잡도: O(1)
입력 및 출력 예시
Input:
정렬되지 않은 데이터 목록: 108 96 23 74 12 56 85 42 13 47
Output:
정렬 전 배열: 108 96 23 74 12 56 85 42 13 47
정렬 후 배열: 12 13 23 42 47 56 74 85 96 108
알고리즘
CombSort(array, size)
입력 − 데이터 배열과 배열 내 전체 요소의 개수
출력 − 정렬된 배열
Begin
gap := size
flag := true
while gap ≠ 1 OR flag = true do
gap = floor(gap/1.3) // 나눈 후의 내림(floor) 값
if gap < 1 then
gap := 1
flag = false
for i := 0 to size – gap -1 do
if array[i] > array[i+gap] then
swap array[i] with array[i+gap]
flag = true;
done
done
End
C++ 구현 예제
#include<iostream>
#include<algorithm>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void combSort(int *array, int size) {
int gap = size; // 간격 초기값을 배열 크기로 설정
bool flag = true;
while(gap != 1 || flag == true) {
gap = (gap*10)/13; // 감소 계수로 간격 축소
if(gap<1)
gap = 1;
flag = false;
for(int i = 0; i<size-gap; i++) { // 간격만큼 떨어진 요소 비교
if(array[i] > array[i+gap]) {
swap(array[i], array[i+gap]);
flag = true;
}
}
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
combSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
실행 결과
Enter the number of elements: 10
Enter elements:
108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108