빗질 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox algorithm
|class=[[정렬 알고리즘]]
|image=[[파일:comb_sort_demo.gif|빗질 정렬 시각화]]
|caption=Comb sort with shrink factor ''k''=1.24733
|data=[[배열]]
|time=<math>O(n^2)</math><ref name="BB"/>
|average-time=<math>\Omega(n^2/2^p)</math>: 여기서 {{math|''p''}}는 증가 수<ref name=BB/>
|best-time=<math>\Theta(n \log n)</math>
|space=<math>O(1)</math>
|optimal=
}}
'''빗질 정렬'''({{lang|en|comb sort}})은 [[버블 정렬]]을 개선한 정렬 알고리즘으로, 1980년 Włodzimierz Dobosiewicz가 설계하였다. 다른 정렬 알고리즘에 비해 상대적으로 단순하다.<ref name=BB>{{저널 인용| doi = 10.1016/S0020-0190(00)00223-4| title = Analyzing variants of Shellsort| journal = [[Information Processing Letters|Inf. Process. Lett.]]| volume = 79| issue = 5| pages = 223–227
| date = 15 September 2001| last1 = Brejová | first1 = B. }}</ref><ref>{{저널 인용
 |title=An efficient variation of bubble sort
 |author=Wlodzimierz Dobosiewicz
 |journal=Information Processing Letters
 |volume=11
 |year=1980
 |pages=5–6
 |doi=10.1016/0020-0190(80)90022-8
}}</ref>
1991년에 스테판 레이시({{llang|en|Stephen Lacey}})와 리차드 박스({{llang|en|Richard Box}})가 재발견하였다.<ref>[http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm "A Fast Easy Sort"] {{웹아카이브|url=https://web.archive.org/web/20120414204046/http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm}}, [[Byte Magazine|''Byte'' Magazine]], April 1991</ref>

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

=== 의사코드 ===

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

=== [[파이썬]] ===
<syntaxhighlight lang="python3">
import math

def comb_sort(arr):
    gap = len(arr)
    shrink = 1.3
    sorted = False

    while not sorted:
        gap = math.floor(gap / shrink)

        if gap > 1:
            sorted = False
        else:
            gap = 1
            sorted = True
        
        i = 0
        while i + gap < len(arr):
            if arr[i] > arr[i+gap]:
                arr[i], arr[i+gap] = arr[i+gap], arr[i]
                sorted = False

            i = i + 1
    
    return arr
</syntaxhighlight>

== 같이 보기 ==
* [[거품 정렬]]
* [[칵테일 정렬]]

== 각주 ==
{{각주}}

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:비교 정렬]]