라이브러리 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|class=[[정렬 알고리즘]]
|image=
|data=[[배열]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time=<math>O(n\log n)</math>
|space=<math>O(n)</math>
|optimal=?
}}
'''라이브러리 정렬'''({{lang|en|library sort}}, 라이브러리 소트, gapped insertion sort)은 [[삽입 정렬]]을 사용하지만 차후의 삽입 속도를 빠르게 하기 위해 배열에 간격을 두는 [[정렬 알고리즘]]의 하나이다.

이 알고리즘은 2004년 마이클 A. 벤더, Martin Farach-Colton, 미구엘 모스테이로에 의해 제안되었으며<ref>{{ArXiv 인용|arxiv=cs/0407003 |title=Insertion Sort is O(n log n) |date=1 July 2004 |last1=Bender |first1=Michael A. |last2=Farach-Colton |first2=Martín |authorlink2=Martin Farach-Colton |last3=Mosteiro |first3=Miguel A.}}</ref> 2006년 출판되었다.<ref name="definition">{{저널 인용 | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391–397 | date=June 2006 | last1=Bender | first1=Michael A. | last2=Farach-Colton | first2=Martín | authorlink2=Martin Farach-Colton | last3=Mosteiro | first3=Miguel A. | title=Insertion Sort is O(n log n) | doi=10.1007/s00224-005-1237-z | url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | arxiv=cs/0407003 | 확인날짜=2019-11-20 | 보존url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | 보존날짜=2017-09-08 | url-status=dead }}</ref>

기반을 둔 삽입 정렬처럼 라이브러리 정렬은 [[안정 정렬|안정]] [[비교 정렬]]에 속하며 [[온라인 알고리즘]]으로 수행할 수 있다. 그러나 삽입 정렬의 O(n<sup>2</sup>)보다 [[퀵 정렬]]에 맞먹는 O(n log n)의 실행 시간을 보일 가능성이 높은 것으로 입증되었다. 이러한 개선을 위해 사용되는 구조는 [[스킵 리스트]]의 것과 매우 비슷하다.

== 구현 ==
=== 의사 코드 ===
 '''proc''' rebalance(A, begin, end)
     r ← end
     w ← end * 2
     '''while''' r >= begin
         A[w+1] ← gap
         A[w] ← A[r]
         r ← r - 1
         w ← w - 2

 '''proc''' sort(A)
     n ← length(A)
     S ← new array of n gaps
     '''for''' i ← 1 to floor(log2(n) + 1)
         '''for''' j ← 2^i to 2^(i+1)
             ins ← binarysearch(A[j], S, 2^(i-1))
             insert A[j] at S[ins]

== 각주 ==
{{각주}}

== 외부 링크 ==
* [http://www.cs.sunysb.edu/~bender/newpub/BenderFaMo06-librarysort.pdf Gapped Insertion Sort]

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:비교 정렬]]
[[분류:안정 정렬]]
[[분류:온라인 정렬]]