빗질 정렬은 상대적으로 단순한 정렬 알고리즘으로, 버블 정렬을 개선한 알고리즘이다.
기본적인 개념은, '거북이'라고 부르는 목록의 끝 가까이에 있는, 크기가 작은 값들을 제거하는 것이다.
버블 정렬에서 정렬의 속도를 떨어트리는 요소들이 위 값들이기 때문이다.
반대로 '토끼'라고 부르는 목록의 처음 가까이에 있는, 크기가 큰 값들은 버블 정렬에서 문제가 되지 않는다.
버블 정렬에서 두 요소들이 비교될 때, 항상 두 값 사이의 거리를 나타내는 값인 격차는 항상 1이다.
빗질 정렬에서는 이 격차가 1이상이 되어도 된다는 특징을 가진다.
동작 순서는 다음과 같다.
목록의 길이가 n이고, 수축 계수가 k라고 했을 때, 격차를 n/k로 설정하여 요소들을 비교/교환한다.
교환이 끝난 뒤 다시 수축 계수에 의해 격차를 나누고, 또 새로운 격차로 목록을 분류하는 방식으로 격차가 1이 될 때 까지 이것을 반복한다.
최종 단계에서는 버블 정렬과 같은 방식이지만, 이때는 대부분의 '거북이'들이 처리되었기 때문에 효율적으로 정렬이 가능하다.
아래 그림은 수축 계수가 1.24733인 빗질 정렬의 동작을 나타낸 것이다.
