난쟁이 정렬

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

난쟁이 정렬

그놈 정렬의 시각화
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	${\displaystyle O(n^{2})}$
최선 시간복잡도	${\displaystyle O(n)}$
평균 시간복잡도	${\displaystyle O(n^{2})}$
공간복잡도	${\displaystyle O(1)}$ 보조

의사코드

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

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