빗질 정렬

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
빗질 정렬
빗질 정렬 시각화
Comb sort with shrink factor k=1.24733
분류정렬 알고리즘
자료 구조배열
최악 시간복잡도[1]
최선 시간복잡도
평균 시간복잡도: 여기서 p는 증가 수[1]
공간복잡도

빗질 정렬(comb sort)은 1980년 Włodzimierz Dobosiewicz가 설계한 상대적으로 단순한 정렬 알고리즘이다.[1][2] 나중에 1991년에 Stephen Lacey와 Richard Box가 재발견하였다.[3] 빗질 정렬은 거품 정렬을 개선한다.

알고리즘[편집]

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

의사코드[편집]

 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

같이 보기[편집]

각주[편집]

  1. Brejová, B. (2001년 9월 15일). “Analyzing variants of Shellsort”. 《Inf. Process. Lett.79 (5): 223–227. doi:10.1016/S0020-0190(00)00223-4. 
  2. Wlodzimierz Dobosiewicz (1980). “An efficient variation of bubble sort”. 《Information Processing Letters》 11: 5–6. doi:10.1016/0020-0190(80)90022-8. 
  3. "A Fast Easy Sort", Byte Magazine, April 1991