라이브러리 정렬

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

라이브러리 정렬

클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O(n^{2})}$
베스트 케이스 공연	${\displaystyle O(n\log n)}$
평균 공연	${\displaystyle O(n\log n)}$
최악의 경우 공간 복잡성	${\displaystyle O(n)}$

라이브러리 정렬 또는 줄 바꿈 삽입 정렬은 삽입 정렬을 사용하지만 배열의 간격이 있는 정렬 알고리즘으로 이후 삽입을 가속화한다.그 이름은 다음과 같은 비유에서 유래되었다.

사서 한 사람이 그들의 책을 알파벳 순으로 긴 선반에 보관하고, 왼쪽 끝에 있는 A부터 시작하여 Z가 끝날 때까지 책 사이에 공백이 없는 선반을 따라 오른쪽으로 계속 보관한다고 가정해보자.사서가 B섹션에 속하는 새 책을 취득했다면, 일단 B섹션에서 정확한 공간을 찾으면, 새 책의 공간을 마련하기 위해 B스 가운데에서 Z스까지 모든 책을 옮겨야 할 것이다.이것은 삽입 분류다.그러나 그들이 B 뒤에 아직 공간이 있는 한, 편지마다 한 칸씩을 남겨둔다면, 새 책을 놓을 공간을 만들기 위해 몇 권의 책만 옮기면 될 것이다.이것이 도서관 분류의 기본 원칙이다.

이 알고리즘은 마이클 A에 의해 제안되었다. 벤더, 마르틴 파라흐-콜튼, 미겔 모스테이로 등이 2004년에^[1] 출판되어 2006년에 출판되었다.^[2]

라이브러리 정렬은 그것이 기초하는 삽입 정렬과 마찬가지로 비교 정렬이지만, 삽입 정렬의 O(n²)가 아닌 O(n log n) 시간(퀵소트)으로 실행될 확률이 높은 것으로 나타났다.논문에서 주어진 완전한 구현이나 삽입과 재조정과 같은 중요한 부분의 정확한 알고리즘은 없다.도서관 분류의 효율성이 실제 다른 분류 방법과 어떻게 비교되는지를 논의하기 위해 추가 정보가 필요할 것이다.

기본 삽입 분류와 비교해 라이브러리 분류의 단점은 공백에 여분의 공간이 필요하다는 점이다.그 공간의 양과 분포는 구현에 의존할 것이다.논문에서 필요한 배열의 크기는 (1 + ε)n이지만, ^[2]ε을 선택하는 방법에 대한 추가 권장사항은 없다.게다가 적응하지도 안정적이지도 않다.높은 확률의 시간 범위를 보장하려면 입력을 무작위로 허용해야 하며, 이는 동일한 요소의 상대적 순서를 변경하고 사전 편향된 입력을 섞어야 한다.또한 알고리즘은 바이너리 검색을 사용하여 각 요소에 대한 삽입점을 찾는데, 이는 사전 편중된 입력의 이익을 취하지 않는다.

임의로 입력을 섞을 수 없기 때문에 온라인 알고리즘으로 실행할 수 없는 것도 단점이다.이 흔들림 없이 사용하면 이차적인 행동으로 쉽게 변질될 수 있다.

삽입 분류의 한 가지 약점은 메모리 쓰기가 비싸면 많은 수의 스왑 작업이 필요하고 비용이 많이 든다는 것이다.공간을 만들기 위해 이동해야 하는 요소가 적기 때문에 삽입 단계에서 라이브러리 정렬이 다소 개선될 수 있지만, 균형 조정 단계에서 추가 비용을 추가한다.또한 랜덤 데이터 집합에서 삽입할 때마다 특히 대용량 데이터 집합에서 더 이상 캐시에 저장되지 않는 메모리에 액세스할 수 있기 때문에 참조 위치도 병합에 비해 좋지 않을 것이다.

실행

알고리즘.

우리가 n개의 원소를 가지고 있다고 하자.우리는 우리가 주고자 하는 간격을 선택한다.그러면 우리는 최종적인 크기 (1 + ))n을 갖게 될 것이다.알고리즘은 로그 n 라운드에서 작동한다.각 라운드에서 배열을 다시 밸런싱하기 전에 최종 배열에 이미 있는 만큼의 요소를 삽입한다.삽입 위치를 찾기 위해 최종 배열에 바이너리 검색을 적용한 후 빈 공간에 도달할 때까지 다음 요소를 교환한다.라운드가 끝나면 각 요소 사이에 공백을 삽입하여 최종 배열을 다시 밸런싱한다.

알고리즘의 세 가지 중요한 단계는 다음과 같다.

1. 이진 검색: 이미 삽입된 요소 내에서 이진 검색을 적용하여 삽입 위치 찾기이것은 중간 요소의 빈 공간에 부딪히면 배열의 왼쪽이나 오른쪽을 향해 선형적으로 움직이면 된다.
2. 삽입:발견된 위치에 요소를 삽입하고 빈 공간에 도달할 때까지 다음 요소를 1개씩 스와핑하십시오.이것은 로그 시간으로, 높은 확률로 이루어진다.
3. 재균형 조정:배열의 각 요소 쌍 사이에 공백 삽입재조정 비용은 이미 삽입된 요소의 수에서 선형이다.각 라운드에 대해 2의 힘으로 이러한 길이가 증가함에 따라, 재균형의 총 비용 또한 선형적이다.

가성음

절차 재조정(A, 시작, 끝)은 r end w end end end end end end end gap gap gap gap gap gap 갭 A[w] ← gap r r r - 1 w - 2

절차 정렬(A)은 n ← 길이(A) S ← n 간격의 n array 새 배열로 i ← 1 ~ 바닥(log2(n) + 1) j ← 2^i ~ 2^(i + 1) do ins ins binary search(A[j], S, 2^(i - 1) s[ins]에 A[j] 삽입

여기binarysearch(el, A, k)A의 첫 번째 k 요소에서 간격을 건너뛰고 이진 검색을 수행하여 요소 엘을 찾을 수 있는 위치를 찾으십시오.삽입은 채워진 요소보다 간극을 선호해야 한다.

참조

외부 링크

• 게핑된 삽입 정렬