난쟁이 정렬

난쟁이 정렬, 그놈 정렬(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로 나타낸다.

각주

외부 링크 
 Gnome sort

정렬 알고리즘
비교 정렬
안정 정렬