Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Library_sort> ?p ?o. }
Showing items 1 to 42 of
42
with 100 items per page.
- Library_sort 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 his books alphabetically on a long shelf, starting with the A's at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Z's. If the librarian acquired a new book that belongs to the B section, once he finds the correct space in the B section, he will have to move every book over, from the middle of the B's all the way down to the Z's in order to make room for the new book. This is an insertion sort. However, if he were to leave a space after every letter, as long as there was still space after B, he 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 Miguel Mosteiro in 2004 and published 2006.Like the insertion sort it is based on, library sort is a stable comparison sort and can be run as an online algorithm; 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). The mechanism used for this improvement is very similar to that of a skip list. 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 library sort efficiency compares to 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 ε. 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.".
- Library_sort wikiPageExternalLink BenderFaMo06-librarysort.pdf.
- Library_sort wikiPageID "2448633".
- Library_sort wikiPageRevisionID "588370483".
- Library_sort class Sorting_algorithm.
- Library_sort data Array_data_structure.
- Library_sort hasPhotoCollection Library_sort.
- Library_sort optimal "?".
- Library_sort subject Category:Comparison_sorts.
- Library_sort subject Category:Online_sorts.
- Library_sort subject Category:Sorting_algorithms.
- Library_sort subject Category:Stable_sorts.
- Library_sort type Abstraction100002137.
- Library_sort type Act100030358.
- Library_sort type Activity100407535.
- Library_sort type Algorithm105847438.
- Library_sort type Category105838765.
- Library_sort type Cognition100023271.
- Library_sort type ComparisonSorts.
- Library_sort type Concept105835747.
- Library_sort type Content105809192.
- Library_sort type Event100029378.
- Library_sort type Idea105833840.
- Library_sort type Kind105839024.
- Library_sort type OnlineSorts.
- Library_sort type Procedure101023820.
- Library_sort type PsychologicalFeature100023100.
- Library_sort type Rule105846932.
- Library_sort type SortingAlgorithm105847658.
- Library_sort type SortingAlgorithms.
- Library_sort type StableSorts.
- Library_sort type YagoPermanentlyLocatedEntity.
- Library_sort comment "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 his books alphabetically on a long shelf, starting with the A's at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Z's.".
- Library_sort label "Library sort".
- Library_sort label "Sortowanie biblioteczne".
- Library_sort sameAs Sortowanie_biblioteczne.
- Library_sort sameAs m.07dvhs.
- Library_sort sameAs Q3495147.
- Library_sort sameAs Q3495147.
- Library_sort sameAs Library_sort.
- Library_sort wasDerivedFrom Library_sort?oldid=588370483.
- Library_sort isPrimaryTopicOf Library_sort.