빗질 정렬

빗질 정렬()은 버블 정렬을 개선한 정렬 알고리즘으로, 1980년 Włodzimierz Dobosiewicz가 설계하였다. 다른 정렬 알고리즘에 비해 상대적으로 단순하다.
1991년에 스테판 레이시()와 리차드 박스()가 재발견하였다.

알고리즘 
기본 개념은 리스트의 끝 가까이의 작은 값들("거북이"라고 함)을 제거하는 것인데, 그 이유는 거품 정렬이 이 상황에서 정렬의 속도를 떨어트리기 때문이다. 목록 처음 가까이에 있는 큰 값들("토끼"라고 함)은 거품 정렬에 문제를 일으키지 않는다.

의사코드 

  function combsort(array input)
     gap := input.size // Initialize gap size
     shrink := 1.3 // Set the gap shrink factor
     sorted := false
     loop while sorted = false
         // Update the gap value for a next comb
         gap := floor(gap / shrink)
         if gap > 1
             sorted := false // We are never sorted as long as gap > 1
         else
             gap := 1
             sorted := true // If there are no swaps this pass, we are done
         end if
         // A single "comb" over the input list
         i := 0
         loop while i + gap < input.size // See Shell sort for a similar idea
             if input[i] > input[i+gap]
                 swap (input[i], input[i+gap])
                 sorted := false
                 // If this assignment never happens within the loop,
                 // then there have been no swaps and the list is sorted.
              end if
              i := i + 1
          end loop
          
      end loop
  end function

같이 보기 
 거품 정렬
 칵테일 정렬

각주 

정렬 알고리즘
비교 정렬