Gnome sort

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Gnome sort" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

Gnome sort

최적화된 Gnome 정렬의 시각화 이 기사 또는 섹션은 오해의 소지가 있는 부분을 포함할 수 있다. 토크 페이지에 제시된 모든 제안에 따라 이 기사를 명확히 할 수 있도록 도와주십시오. .
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O(n^{2})}$
베스트 케이스 공연	${\displaystyle O(n)}$
평균 공연	${\displaystyle O(n^{2})}$
최악의 경우 공간 복잡성	${\displaystyle O}$( ${\displaystyle 1}$) ${\displaystyle$ O$(1)}$ 보조$$

Gnome sort(이중 바보 sort)는 이란의 컴퓨터 과학자 Hamid Sarbazi-Azad(샤리프 공과대학 컴퓨터과학공학과 교수)^[1]가 2000년 제안한 분류 알고리즘이다. 이 분류는 처음에는 (거짓말과 혼동되지 않기 위해) 바보^[2] 같은 분류라고 불렸으며, 나중에 딕 그루네에 의해 묘사되어 gnome 분류라고 명명되었다.^[3]

gnome sort는 한 번에 한 항목과 함께 작동하지만 일련의 스왑을 통해 해당 항목을 적절한 위치에 배치한다는 점에서 삽입 정렬 알고리즘과 유사한 것이다. 그것은 내포된 루프가 필요 없는 개념적으로 간단하다. 평균 가동 시간은 O(n²)이지만, 목록이 처음에 거의 정렬되어 있으면 O(n) 쪽으로 기울어진다.^{[4][note 1]}

알고리즘은 인접한 두 원소의 순서가 틀린 곳을 먼저 찾아 스와핑한다. 그것은 스왑을 수행하면 이전에 교환된 요소 옆에 새로운 순서가 맞지 않는 인접 쌍을 도입할 수 있다는 사실을 이용한다. 현재 위치의 전방 요소가 정렬된다고 가정하지 않기 때문에 스와핑된 요소 바로 앞의 위치만 확인하면 된다.

설명

딕 그루네는 다음과 같은 이야기로 분류 방법을 설명했다.^[3]

Gnome Sort는 표준 네덜란드 가든 Gnome(Du.: tuinkabouter)에서 사용하는 기술을 기반으로 한다.
정원 지놈은 이렇게 화분 한 줄을 분류한다.
기본적으로 옆에 있는 화분과 앞의 화분을 보고, 순서가 맞으면 한 화분을 앞으로 내딛고, 그렇지 않으면 화분을 바꿔서 한 화분을 뒤로 내딛는다.
경계 조건: 이전의 항아리가 없으면 앞으로 나아가고, 옆에 항아리가 없으면 끝난다.

— "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com

코드

0 기반 배열을 사용하는 gnome 정렬에 대한 유사 코드:

procedure gnomeSort(a]): pos : 0, pos < length(a): pos : (pos == 0 또는 a[pos] >= a: pos + 다른 1: swap a[pos] 및 a[pos-1] pos := pos - 1 

예

정렬되지 않은 배열인 a = [5, 3, 2, 4]를 지정하면 gnome 정렬은 루프 중에 다음 단계를 수행한다. 현재 위치가 굵게 강조 표시되고 변수 값으로 표시됨 pos.

최적화

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. (2015년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

목록의 시작 부분으로 다시 이동하기 전에 위치를 저장하는 변수를 도입하여 gnome 정렬을 최적화할 수 있다. 이 최적화와 함께 gnome 종류는 삽입 종류의 변형이 될 것이다.

0 기반 배열을 사용하여 최적화된 gnome 정렬에 대한 유사 코드:

절차 최적화GnomeSort(a[]):     1 ~ 길이(a):         gnomeSort(a, pos)  프로시저 gnomeSort(a[], upperBound):      pos :=상위 경계     pos > 0과 a[pos-1] > a[pos] 동안:          a[pos-1]와 a[pos]를 교환하다         pos := pos - 1 

메모들

참조

외부 링크

Wikibook 알고리즘 구현에는 Gnome 정렬을 주제로 한 페이지가 있다.

• Gnome sort