난쟁이 정렬

위키백과, 우리 모두의 백과사전.

난쟁이 정렬
Visualization of Gnome sort.gif
그놈 정렬의 시각화
분류정렬 알고리즘
자료 구조배열
최악 시간복잡도
최선 시간복잡도
평균 시간복잡도
공간복잡도 보조

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

의사코드[편집]

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

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

각주[편집]

  1. Hamid, Sarbazi-Azad. “Hamid Sarbazi-Azad profile page”. 2018년 10월 16일에 원본 문서에서 보존된 문서. 2018년 10월 16일에 확인함. 
  2. Sarbazi-Azad, Hamid (2000년 10월 2일). “Stupid Sort: A new sorting algorithm” (PDF). 《Newsletter》 (Computing Science Department, Univ. of Glasgow) (599): 4. 2012년 3월 7일에 원본 문서 (PDF)에서 보존된 문서. 2014년 11월 25일에 확인함. 
  3. “Gnome Sort - The Simplest Sort Algorithm”. 《Dickgrune.com》. 2000년 10월 2일. 2017년 8월 31일에 원본 문서에서 보존된 문서. 2017년 7월 20일에 확인함. 

외부 링크[편집]