콤 정렬(Comb Sort)이란?
콤 정렬(Comb Sort)은 버블 정렬(Bubble Sort)을 개선한 정렬 알고리즘입니다. 리스트 끝부분에 몰려 있는 작은 값들을 빠르게 앞쪽으로 이동시키고, 배열 내의 역전(inversion) 요소를 하나씩 해소해 나가며 정렬을 완성합니다.
버블 정렬이 항상 인접한 두 요소만 비교하는 것과 달리, 콤 정렬은 일정 간격(gap)을 두고 요소를 비교·교환하기 때문에 '거북이(turtle)'라고 불리는 작은 값들이 배열 끝에 남아 성능을 저하시키는 문제를 효과적으로 해결합니다.
예제 코드
다음은 자바로 작성한 콤 정렬의 전체 구현 예제입니다.
import java.util.Arrays;
public class Demo{
void comb_sort(int nums[]){
int len_gap = nums.length;
float shrink_val = 1.3f;
boolean swap = false;
while (len_gap > 1 || swap) {
if (len_gap > 1) {
len_gap = (int)(len_gap / shrink_val);
}
swap = false;
for (int i = 0; len_gap + i < nums.length; i++){
if (nums[i] > nums[i + len_gap]) {
swap(nums, i, i + len_gap);
swap = true;
}
}
}
}
private static void swap(int nums[], int x, int y) {
Integer temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
public static void main(String args[]){
Demo ob = new Demo();
int nums[] = {6, 78, 90, -12, -45, 0, -1, 45};
System.out.println("The original array contains ");
System.out.println(Arrays.toString(nums));
ob.comb_sort(nums);
System.out.println("The sorted array is ");
System.out.println(Arrays.toString(nums));
}
}실행 결과
위 코드를 실행하면 다음과 같이 정렬 전 배열과 정렬 후 배열이 출력됩니다.
The original array contains [6, 78, 90, -12, -45, 0, -1, 45] The sorted array is [-45, -12, -1, 0, 6, 45, 78, 90]
코드 동작 원리
Demo 클래스와 comb_sort 함수: Demo라는 이름의 클래스 안에 'comb_sort' 함수가 정의되어 있습니다. 이 함수가 실제 콤 정렬 로직을 수행합니다.
갭(gap) 계산: 먼저 배열의 길이를 초기 갭 값으로 설정합니다. 이후 반복이 진행될 때마다 현재 갭이 1보다 크면, 배열 길이를 축소 비율(shrink factor)인 1.3f로 나눈 값을 새로운 'len_gap'으로 사용합니다. 1.3이라는 축소 비율은 실험적으로 가장 좋은 성능을 보이는 값으로 널리 알려져 있습니다.
요소 비교 및 교환: 배열을 처음부터 순회하면서 현재 요소와 'len_gap'만큼 떨어진 요소를 비교합니다. 만약 앞의 요소가 더 크다면 두 요소의 위치를 서로 교환(swap)하고, 교환이 발생했음을 표시하기 위해 'swap' 플래그를 true로 설정합니다.
반복 종료 조건: 갭이 1이 되면 사실상 버블 정렬과 동일하게 동작하며, 더 이상 교환이 발생하지 않을 때까지(swap이 false가 될 때까지) 반복하여 배열을 완전히 정렬합니다.
main 함수: main 메서드에서는 정렬할 배열을 정의하고, Demo 클래스의 인스턴스를 생성한 뒤 해당 배열을 인자로 'comb_sort' 함수를 호출합니다. 정렬 전후의 배열 상태는 Arrays.toString() 메서드를 통해 콘솔에 출력됩니다.
마무리
콤 정렬은 구현이 간단하면서도 버블 정렬보다 평균적으로 뛰어난 성능을 보여주는 알고리즘입니다. 평균 시간 복잡도는 O(n²/2^p) 수준으로 알려져 있으며, 최악의 경우 O(n²)입니다. 추가적인 메모리 공간이 거의 필요 없는 제자리(in-place) 정렬 방식이기 때문에 학습용 예제나 소규모 데이터 정렬에 활용하기 좋습니다.