난쟁이 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|name=난쟁이 정렬|class=[[정렬 알고리즘]]
|image=Visualization of Gnome sort.gif
|caption=그놈 정렬의 시각화
|data=[[배열]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time= <math>O(n^2)</math>
|space= <math>O(1)</math> 보조
}}

'''난쟁이 정렬''', '''그놈 정렬'''(Gnome sort), '''스투피드 정렬'''(stupid sort)은 루프 안의 루프를 사용하지 않는 [[삽입 정렬]] [[정렬 알고리즘]]의 일종이다. 난쟁이 정렬은 [[이란]]의 컴퓨터 과학자 하미드 사바지-아자드(Hamid Sarbazi-Azad)에 의해 2000년 처음 제안되었다.<ref>{{웹 인용|url=http://sharif.edu/~azad/|title=Hamid Sarbazi-Azad profile page|last=Hamid|first=Sarbazi-Azad|archive-url=https://web.archive.org/web/20181016164904/http://sharif.edu/~azad/#|archive-date=2018-10-16|url-status=live|access-date=October 16, 2018}}</ref> 이 정렬은 처음으로 스투피드 정렬(stupid sort)로 불리게 되었고<ref>{{저널 인용
 |last         = Sarbazi-Azad
 |first        = Hamid
 |date         = 2 October 2000
 |title        = Stupid Sort: A new sorting algorithm
 |url          = http://sina.sharif.edu/~azad/stupid-sort.PDF
 |journal      = Newsletter
 |publisher    = Computing Science Department, Univ. of Glasgow
 |issue        = 599
 |page         = 4
 |access-date   = 25 November 2014
 |archive-url  = https://web.archive.org/web/20120307235904/http://sina.sharif.edu/~azad/stupid-sort.PDF
 |archive-date = 7 March 2012
 |url-status   = live
}}</ref>([[보고정렬]]과 구분) 나중에 [[딕 그룬]]에 의해 설명되면서 '그놈 정렬'(난쟁이 정렬)로 명명되었다.<ref name="DGrune">{{웹 인용|url=http://www.dickgrune.com/Programs/gnomesort.html |title=Gnome Sort - The Simplest Sort Algorithm |website=Dickgrune.com |date=2000-10-02 |access-date=2017-07-20 |archive-url=https://web.archive.org/web/20170831222005/https://dickgrune.com/Programs/gnomesort.html# |archive-date=2017-08-31 |url-status=live }}</ref>

== 의사코드 ==
제로 기반 배열을 사용한 난쟁이 정렬의 [[의사코드]]는 다음과 같다.

<syntaxhighlight lang="text">
procedure gnomeSort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1
</syntaxhighlight>

=== 예시 ===
a = [5, 3, 2, 4]라는 정렬되지 않은 배열이 있다고 가정할 때 난쟁이 정렬은 while 루프 중에 다음 단계들을 수행한다. 현재의 위치는 '''굵게''' 표시되어 있으며 변수의 값은 <code>pos</code>로 나타낸다.
{|    class="wikitable"
|-
! 현재 배열
! <code>pos</code>
! 영향을 받는 조건
! 취해야 할 동작
|-
||    ['''5''', 3, 2, 4] || 0 ||    pos == 0  || increment pos
|-
||    [5, '''3''', 2, 4] || 1 ||    a[pos] < a[pos-1]  || swap, decrement pos
|-
||    ['''3''', 5, 2, 4] || 0 ||    pos == 0  || increment pos
|-
||    [3, '''5''', 2, 4] || 1 ||    a[pos] ≥ a[pos-1] || increment pos
|-
||    [3, 5, '''2''', 4] || 2 ||    a[pos] < a[pos-1] || swap, decrement pos
|-
||    [3, '''2''', 5, 4] || 1 ||    a[pos] < a[pos-1] || swap, decrement pos
|-
||    ['''2''', 3, 5, 4] || 0 ||    pos == 0  || increment pos
|-
||    [2, '''3''', 5, 4] || 1 ||    a[pos] ≥ a[pos-1] || increment pos
|-
||    [2, 3, '''5''', 4] || 2 ||    a[pos] ≥ a[pos-1] || increment pos:
|-
||    [2, 3, 5, '''4'''] || 3 ||    a[pos] < a[pos-1] || swap, decrement pos
|-
||    [2, 3, '''4''', 5] || 2 ||    a[pos] ≥ a[pos-1] || increment pos
|-
||    [2, 3, 4, '''5'''] || 3 ||    a[pos] ≥ a[pos-1] || increment pos
|-
||    [2, 3, 4, 5]       || 4 ||    pos == length(a) || finished
|}

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

== 외부 링크 ==
* [http://dickgrune.com/Programs/gnomesort.html Gnome sort]

{{정렬 알고리즘}}

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