난쟁이 정렬

난쟁이 정렬, 그놈 정렬(Gnome sort), 스투피드 정렬(stupid sort)은 루프 안의 루프를 사용하지 않는 삽입 정렬 정렬 알고리즘의 일종이다. 난쟁이 정렬은 이란의 컴퓨터 과학자 하미드 사바지-아자드(Hamid Sarbazi-Azad)에 의해 2000년 처음 제안되었다. 이 정렬은 처음으로 스투피드 정렬(stupid sort)로 불리게 되었고(보고정렬과 구분) 나중에 딕 그룬에 의해 설명되면서 '그놈 정렬'(난쟁이 정렬)로 명명되었다.

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

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

 예시 
a = [5, 3, 2, 4]라는 정렬되지 않은 배열이 있다고 가정할 때 난쟁이 정렬은 while 루프 중에 다음 단계들을 수행한다. 현재의 위치는 굵게 표시되어 있으며 변수의 값은 pos로 나타낸다.
 현재 배열 pos 영향을 받는 조건 취해야 할 동작    [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

 각주 

 외부 링크 
 Gnome sort

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