Library sort (original) (raw)
라이브러리 정렬(library sort, 라이브러리 소트, gapped insertion sort)은 삽입 정렬을 사용하지만 차후의 삽입 속도를 빠르게 하기 위해 배열에 간격을 두는 정렬 알고리즘의 하나이다. 이 알고리즘은 2004년 마이클 A. 벤더, Martin Farach-Colton, 미구엘 모스테이로에 의해 제안되었으며 2006년 출판되었다. 기반을 둔 삽입 정렬처럼 라이브러리 정렬은 안정 비교 정렬에 속하며 온라인 알고리즘으로 수행할 수 있다. 그러나 삽입 정렬의 O(n2)보다 퀵 정렬에 맞먹는 O(n log n)의 실행 시간을 보일 가능성이 높은 것으로 입증되었다. 이러한 개선을 위해 사용되는 구조는 의 것과 매우 비슷하다.
| Property | Value |
|---|---|
| dbo:abstract | Library sort, or gapped insertion sort is a sorting algorithm that uses an insertion sort, but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy: Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort. The algorithm was proposed by Michael A. Bender, Martín Farach-Colton, and in 2004 and was published in 2006. Like the insertion sort it is based on, library sort is a comparison sort; however, it was shown to have a high probability of running in O(n log n) time (comparable to quicksort), rather than an insertion sort's O(n2). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality. Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would be implementation dependent. In the paper the size of the needed array is (1 + ε)n, but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the with-high-probability time bounds, it requires to randomly permute the input, what changes the relative order of equal elements and shuffles any presorted input. Also, the algorithm uses binary search to find the insertion point for each element, which does not take profit of presorted input. Another drawback is that it cannot be run as an online algorithm, because it is not possible to randomly shuffle the input. If used without this shuffling, it could easily degenerate into quadratic behaviour. One weakness of insertion sort is that it may require a high number of swap operations and be costly if memory write is expensive. Library sort may improve that somewhat in the insertion step, as fewer elements need to move to make room, but is also adding an extra cost in the rebalancing step. In addition, locality of reference will be poor compared to mergesort as each insertion from a random data set may access memory that is no longer in cache, especially with large data sets. (en) Library sort es un algoritmo de ordenación que usa ordenación por inserción, pero con espacios vacíos en el arreglo para acelerar inserciones subsiguientes. El nombre proviene de una analogía: Suponga que un bibliotecario almacene sus libros alfabéticamente en una estante, empezando por la A desde la izquierda, y continuando a la derecha a lo largo del estante sin espacios entre los libros hasta que termine por la Z. Si el bibliotecario adquiere un libro nuevo que pertenece a la sección B, una vez que encuentra el espacio correcto en la sección B, tiene que mover cada libro a partir de ese hasta el último libro en la sección Z para abrir espacio al libro nuevo. Esto es ordenación por inserción. Sin embargo, si dejara un espacio vacío después de cada letra, mientras hubiera un espacio vacío después de B, sólo tendría que mover unos cuantos libros para poder ubicar el nuevo libro. Esto es el principio básico de Library Sort. El algoritmo estuvo propuesto por Michael Un. Bender, Martín Farach-Colton, y Miguel Mosteiro en 2004 y estuvo publicado en 2006. Como la ordenación por inserción, Library sort es un algoritmo de ordenamiento por comparación estable y puede ser corrido como un algoritmo en línea; aun así, ha mostrado tener una probabilidad alta de correr en un tiempo O(n log n) (comparable a quicksort), mejor que el tiempo de ordenación por inserción O(n2). El mecanismo utilizado para esta mejora es muy similar a aquello de un skip list.No hay una implementación completa escrita, ni los algoritmos exactos de partes importantes, como la inserción y el re-equilibrio. Sería necesaria más información para discutir cómo la eficiencia de Library sort se compara con otros métodos de ordenamiento en realidad. Comparado a la ordenación por inserción básica, la desventaja de Library sort es que requiere espacio extra para los espacios vacíos. La cantidad y la distribución del espacio extra depende de la implementación. En principio, la medida del arreglo necesitada es (1 + ε)n, pero sin recomendaciones de cómo escoger ε. Una debilidad de ordenación por inserción es que puede requerir un número alto de operaciones de intercambio y ser costoso si la memoria de escritura es costosa. Library sort puede mejorar un poco en el paso de inserción, mientras necesite mover menos elementos para abrir el espacio, pero también está añadiendo un sobrecosto en el paso de re-equilibrio. Además, la ubicación de las referencias será pobre comparado a mergesort ya que cada inserción de un conjunto de datos aleatorio puede acceder a memoria que ya no está en la cache, especialmente con conjuntos de datos grande. (es) 라이브러리 정렬(library sort, 라이브러리 소트, gapped insertion sort)은 삽입 정렬을 사용하지만 차후의 삽입 속도를 빠르게 하기 위해 배열에 간격을 두는 정렬 알고리즘의 하나이다. 이 알고리즘은 2004년 마이클 A. 벤더, Martin Farach-Colton, 미구엘 모스테이로에 의해 제안되었으며 2006년 출판되었다. 기반을 둔 삽입 정렬처럼 라이브러리 정렬은 안정 비교 정렬에 속하며 온라인 알고리즘으로 수행할 수 있다. 그러나 삽입 정렬의 O(n2)보다 퀵 정렬에 맞먹는 O(n log n)의 실행 시간을 보일 가능성이 높은 것으로 입증되었다. 이러한 개선을 위해 사용되는 구조는 의 것과 매우 비슷하다. (ko) 図書館ソートまたはライブラリソート（英: library sort, gapped insertion sort）は、ソートのアルゴリズムの一つ。挿入ソートをベースとし、挿入操作を高速化するために配列に隙間（gap）を設けるもの。名前は次のアナロジーに由来する: 司書が長い本棚にアルファベット順に本を陳列しようとしているとする。本棚は左端がAで始まり、右端のZの終わりまで隙間なく本で埋まっている。司書が新しい本をBの区画に収めるには、Bの区画に適切な位置を見つけ、スペースを空けるために後ろのすべての本をずらす必要がある。これが挿入ソートである。しかし、各区画の間(BとCの境界など)に空白があったなら、新しい本のためにずらすべき本の数は少なくて済む。これが図書館ソートの基本的な原理である。 このアルゴリズムは2004年に、およびによって提案され、2006年に発表された。 図書館ソートはそのベースとなる挿入ソートと同様、安定なであり、オンラインアルゴリズムとして実行可能。しかしながら O(n2) の挿入ソートとは異なり、高確率でクイックソートと同じクラスの O(n log n) で実行できることが示されている。この改良のために使われた仕組みはスキップリストのものとほぼ同様である。論文では、完全な実装も、挿入や調整(rebalance)のような重要な部分の正確なアルゴリズムも示されていない。図書館ソートが他のソートアルゴリズムと比べて現実的にどの程度有効であるかを議論するには、さらなる情報が必要となる。 基本的な挿入ソートと比べて、図書館ソートの欠点は隙間のための空間を要することである。スペースの量や配置は実装による。論文において、必要な配列の長さは (1 + ε)n だとされているが、ε の選び方は何も推奨されていない。 挿入ソートの弱点の一つに、メモリへの書き込みが高コストである時に、多くの回数の swap 操作が負荷になりうるというものがある。図書館ソートは要素の移動が少なくなるように改良されているので、挿入段階が多少改善される可能性があるが、調整の段階で追加のコストを要する。加えて、ランダムなデータセットからの挿入操作がキャッシュから外れたメモリにアクセスする可能性があり、特に大きなデータセットについて、参照の局所性がマージソートに劣る。 (ja) Sortowanie biblioteczne (ang. Library sort) – algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyspieszenia wstawiania elementów. Nazwa wywodzi się z następującej analogii: Wyobraźmy sobie bibliotekarza, który układa książki alfabetycznie na półkach. Zaczynając od książek na literę A ustawia jedną przy drugiej, aż dojdzie do litery Z. Jeśli bibliotekarz postanowi dodać nową książkę na półkę, której nazwa zaczyna się na literę B, to będzie musiał przesunąć wszystkie książki od miejsca, gdzie pasuje nowa książka aż do ostatniej książki. Ponieważ litera B występuje blisko początku alfabetu, więc praktycznie całą półkę książek należy przesunąć. Tak działa sortowanie przez wstawianie. Gdyby jednak bibliotekarz pozostawiał wolne miejsce po każdej literze, to musiałby przesunąć tylko niewielką liczbę książek (dopóki miejsce za literą B by się nie wyczerpało). Na tym polega algorytm Sortowania bibliotecznego. Algorytm zaproponowali: Michael A. Bender, Martín Farach-Colton oraz Miguel Mosteiro w 2004 roku. Podobnie jak sortowanie przez wstawianie, na którym bazuje, sortowanie biblioteczne jest algorytmem stabilnym. Wykazano, że jego złożoność czasowa wynosi najczęściej (podobnie jak algorytmu quicksort), rzadziej (jak przy sortowaniu przez wstawianie). Mankamentem algorytmu jest zwiększone zapotrzebowanie na pamięć. (pl) 图书馆排序，或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻： 假设一名图书管理员在一个长架上按字母顺序來整理书，从左边A開頭的書，一直到右边Z開頭的書，书本之间没有空格。如果图书管理员有一本開頭為B的新书，当他找到了這本書在B區中的正确位置，他将不得不把從該位置後一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母區後留有額外的空間，只要在B區之后還有空间，他插入书時就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。 此算法由 、和 于2004年提出，并于2006年出版。 图书馆排序像插入排序一样，是稳定的排序算法，并且它是在线排序；然而，它被证明在大部分情况下具有O(n log n)的运行速度（相当于快速排序），而不是插入排序的O(n2)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和重新平衡。需要更多的信息来比较图书馆排序的效率与现实中其他排序方法的效率。 相比基本的插入排序，图书馆排序的缺点是需要额外空间。该空间的大小将取决于实作的情況。在本文中，需要的空间为(1+ε)n,，但没有进一步的建议如何选择ε。 插入排序的一个缺点是它可能需要大量的交换操作，并且如果内存写入是昂贵的，则成本很高。图书馆排序可能会在插入步骤中有所改进，因为騰出空間所需移动的次數較少，但也因此在重新平衡步骤中增加了额外的成本。另外，由于随机数据集中的每个插入都可以访问不再处于高速缓存中的内存，特别是对于大型数据集，因此与归并排序相比，引用的局部性将变差。 (zh) |
| dbo:wikiPageExternalLink | http://www.cs.sunysb.edu/~bender/newpub/BenderFaMo06-librarysort.pdf |
| dbo:wikiPageID | 2448633 (xsd:integer) |
| dbo:wikiPageLength | 6458 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1068904331 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbc:Online_sorts dbr:Insertion_sort dbr:Online_algorithm dbr:Comparison_sort dbr:Michael_A._Bender dbc:Comparison_sorts dbc:Sorting_algorithms dbr:Array_data_structure dbc:Stable_sorts dbr:Sorting_algorithm dbr:Mergesort dbr:Martín_Farach-Colton dbr:Binary_search dbr:Miguel_Mosteiro |
| dbp:class | dbr:Sorting_algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:optimal | ? (en) |
| dbp:wikiPageUsesTemplate | dbt:Mvar dbt:Refimprove dbt:Reflist dbt:Infobox_Algorithm dbt:Sorting |
| dcterms:subject | dbc:Online_sorts dbc:Comparison_sorts dbc:Sorting_algorithms dbc:Stable_sorts |
| rdf:type | yago:WikicatComparisonSorts yago:WikicatOnlineSorts yago:WikicatSortingAlgorithms yago:WikicatStableSorts yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | 라이브러리 정렬(library sort, 라이브러리 소트, gapped insertion sort)은 삽입 정렬을 사용하지만 차후의 삽입 속도를 빠르게 하기 위해 배열에 간격을 두는 정렬 알고리즘의 하나이다. 이 알고리즘은 2004년 마이클 A. 벤더, Martin Farach-Colton, 미구엘 모스테이로에 의해 제안되었으며 2006년 출판되었다. 기반을 둔 삽입 정렬처럼 라이브러리 정렬은 안정 비교 정렬에 속하며 온라인 알고리즘으로 수행할 수 있다. 그러나 삽입 정렬의 O(n2)보다 퀵 정렬에 맞먹는 O(n log n)의 실행 시간을 보일 가능성이 높은 것으로 입증되었다. 이러한 개선을 위해 사용되는 구조는 의 것과 매우 비슷하다. (ko) Library sort es un algoritmo de ordenación que usa ordenación por inserción, pero con espacios vacíos en el arreglo para acelerar inserciones subsiguientes. El nombre proviene de una analogía: Suponga que un bibliotecario almacene sus libros alfabéticamente en una estante, empezando por la A desde la izquierda, y continuando a la derecha a lo largo del estante sin espacios entre los libros hasta que termine por la Z. Si el bibliotecario adquiere un libro nuevo que pertenece a la sección B, una vez que encuentra el espacio correcto en la sección B, tiene que mover cada libro a partir de ese hasta el último libro en la sección Z para abrir espacio al libro nuevo. Esto es ordenación por inserción. Sin embargo, si dejara un espacio vacío después de cada letra, mientras hubiera un espacio vacío (es) Library sort, or gapped insertion sort is a sorting algorithm that uses an insertion sort, but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy: Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only (en) 図書館ソートまたはライブラリソート（英: library sort, gapped insertion sort）は、ソートのアルゴリズムの一つ。挿入ソートをベースとし、挿入操作を高速化するために配列に隙間（gap）を設けるもの。名前は次のアナロジーに由来する: 司書が長い本棚にアルファベット順に本を陳列しようとしているとする。本棚は左端がAで始まり、右端のZの終わりまで隙間なく本で埋まっている。司書が新しい本をBの区画に収めるには、Bの区画に適切な位置を見つけ、スペースを空けるために後ろのすべての本をずらす必要がある。これが挿入ソートである。しかし、各区画の間(BとCの境界など)に空白があったなら、新しい本のためにずらすべき本の数は少なくて済む。これが図書館ソートの基本的な原理である。 このアルゴリズムは2004年に、およびによって提案され、2006年に発表された。 基本的な挿入ソートと比べて、図書館ソートの欠点は隙間のための空間を要することである。スペースの量や配置は実装による。論文において、必要な配列の長さは (1 + ε)n だとされているが、ε の選び方は何も推奨されていない。 (ja) Sortowanie biblioteczne (ang. Library sort) – algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyspieszenia wstawiania elementów. Nazwa wywodzi się z następującej analogii: (pl) 图书馆排序，或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻： 假设一名图书管理员在一个长架上按字母顺序來整理书，从左边A開頭的書，一直到右边Z開頭的書，书本之间没有空格。如果图书管理员有一本開頭為B的新书，当他找到了這本書在B區中的正确位置，他将不得不把從該位置後一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母區後留有額外的空間，只要在B區之后還有空间，他插入书時就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。 此算法由 、和 于2004年提出，并于2006年出版。 图书馆排序像插入排序一样，是稳定的排序算法，并且它是在线排序；然而，它被证明在大部分情况下具有O(n log n)的运行速度（相当于快速排序），而不是插入排序的O(n2)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和重新平衡。需要更多的信息来比较图书馆排序的效率与现实中其他排序方法的效率。 相比基本的插入排序，图书馆排序的缺点是需要额外空间。该空间的大小将取决于实作的情況。在本文中，需要的空间为(1+ε)n,，但没有进一步的建议如何选择ε。 (zh) |
| rdfs:label | Library sort (es) Library sort (en) 図書館ソート (ja) 라이브러리 정렬 (ko) Sortowanie biblioteczne (pl) 图书馆排序 (zh) |
| owl:sameAs | freebase:Library sort yago-res:Library sort wikidata:Library sort dbpedia-es:Library sort dbpedia-fa:Library sort http://hy.dbpedia.org/resource/Գրադարանային_տեսակավորում dbpedia-ja:Library sort dbpedia-ko:Library sort dbpedia-pl:Library sort dbpedia-sr:Library sort dbpedia-tr:Library sort dbpedia-zh:Library sort https://global.dbpedia.org/id/3DpDV |
| prov:wasDerivedFrom | wikipedia-en:Library_sort?oldid=1068904331&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Library_sort |
| is dbo:wikiPageRedirects of | dbr:Gapped_insertion_sort |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Insertion_sort dbr:Gapped_insertion_sort dbr:Sorting_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Library_sort |