Library sort: Difference between revisions

Revision as of 14:25, 26 August 2013

Latest revision as of 10:17, 19 January 2025

(42 intermediate revisions by 24 users not shown)

Line 1:

{{Short description|Sorting algorithm}}

{{refimprove|date=October 2017}}

{{Infobox Algorithm

|class=[[Sorting algorithm]]

Line 4 ⟶ 6:

|data=[[Array data structure|Array]]

|time=<math>O(n^2)</math>

|best-time=<math>O(n\log n)</math>

|average-time=<math>O(n\log n)</math>

|space=<math>O(n)</math>

|optimal=?

}}

'''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:<ref>{{Citation | last = Budd | first = Timothy A. | title = An Active Learning approach to Data Structures using C | url = http://classes.engr.oregonstate.edu/eecs/winter2009/cs261/Textbook/Chapter14.pdf}}</ref>

<blockquote>Suppose a librarian were to store histheir books alphabetically on a long shelf, starting with the A'sAs at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Z'sZs. If the librarian acquired a new book that belongs to the B section, once hethey findsfind the correct space in the B section, hethey will have to move every book over, from the middle of the B'sBs all the way down to the Z'sZs in order to make room for the new book. This is an insertion sort. However, if hethey were to leave a space after every letter, as long as there was still space after B, hethey would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arXiv |eprint=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> and was published in 2006.<ref name="definition">{{cite journal | 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 | s2cid=14701669 | access-date=2017-09-07 | archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | archive-date=2017-09-08 | url-status=dead }}</ref>

The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>http://arxiv.org/abs/cs/0407003</ref> and published 2006.<ref name="definition">

{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391 | year=2006 | author=Bender, M. A., Farach-Colton, M., and Mosteiro M. | title=Insertion Sort is O(n log n) | doi = 10.1007/s00224-005-1237-z }}</ref>

Like the insertion sort it is based on, library sort is a [[stable sort|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(n²). 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 efficiency of library sort efficiency 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 bedepend implementationon dependentimplementation. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. OneMoreover, weaknessit ofis [[insertionneither sort]]adaptive isnor thatstable. itIn mayorder requireto awarrant the high-probability numbertime ofbounds, swapit operationsmust andrandomly bepermute costlythe ifinput, memorywhich writechanges isthe expensive.relative Libraryorder sortof mayequal improveelements thatand somewhatshuffles inany thepresorted insertioninput. stepAlso, asthe feweralgorithm elementsuses binary needsearch to movefind tothe makeinsertion room,point butfor iseach alsoelement, addingwhich andoes extranot costtake inadvantage theof rebalancingpresorted stepinput.

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 also adds 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.

==Implementation==

===Algorithm ===

Let us say we have an array of n elements. We choose the gap we intend to give. Then we would have a final array of size (1 + ε)n. The algorithm works in log n rounds. In each round we insert as many elements as there are in the final array already, before re-balancing the array. For finding the position of inserting, we apply Binary Search in the final array and then swap the following elements till we hit an empty space. Once the round is over, we re-balance the final array by inserting spaces between each element.

Let us say we have an array of n elements. We choose the gap we intend to

give. Then we would have a final array of size (1 + ε)n. The algorithm works

in log n rounds. In each round we insert as many elements as there are in

the final array already, before re-balancing the array. For finding the position

of inserting, we apply Binary Search in the final array and then swap the

following elements till we hit an empty space. Once the round is over, we

re-balance the final array by inserting spaces between each element.

Following are three important steps of the algorithm:

# '''Binary Search''': Finding the position of insertion by applying binary search within the already inserted elements. This can be done by linearly moving towards left or right side of the array if you hit an empty space in the middle element.

1. Binary Search:

# '''Insertion''': Inserting the element in the position found and swapping the following elements by 1 position till an empty space is hit. This is done in logarithmic time, with high probability.

Finding the position of insertion by applying binary search within the

# '''Re-Balancing''': Inserting spaces between each pair of elements in the array. The cost of rebalancing is linear in the number of elements already inserted. As these lengths increase with the powers of 2 for each round, the total cost of rebalancing is also linear.

already inserted elements. This can be done by linearly moving towards

left or right side of the array if you hit an empty space in the middle

element.

2. Insertion:

Inserting the element in the position found and swapping the following

elements by 1 position till an empty space is hit.

3. Re-Balancing:

Inserting spaces between each pair of elements in the array. Here

we have used a queue to accomplish this. This takes linear time, and

because there are log n rounds in the algorithm, total re-balancing takes

O(n log n) time only.

===C-Implementation===

<source lang="c">

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define swap(a,b) (a)=(b)+(a)-((b)=(a))

int last,queue[1000008];

//This routine rebalances the array..i.e. inserts the given number of spaces

//in between numbers with the help of a queue

void balance(int f[], int e, int inserted)

{

int top,bottom;

top=bottom=0;

int i=1,s=1,t;

while(s<inserted)

{

t=0;

while(t<e)

{

if(f[i]!=-1)

{

queue[bottom++]=f[i];

}

f[i++]=-1;

t++;

}

if(f[i]!=-1)

queue[bottom++]=f[i];

f[i++]=queue[top++];

s++;

}

last=i-1;

}

//This routine inserts the element in the position found

//by binary search and then swaps the positions of the following

//elements till an empty space is hit

void insert(int f[], int element , int position)

{

if(f[position]==-1)

{

f[position]=element;

if(position>last)

last=position;

}

else

{

int temp=element;

swap(temp,f[position]);

position++;

while(f[position]!=-1)

{

swap(temp,f[position]);

position++;

}

f[position]=temp;

if(position>last)

last=position;

}

}

//This routine applies a binary search on the final array for

//finding the place where the new element will be inserted

void find_place(int f[], int element, int start, int end)

{

int mid=start+((end-start)/2);

if(start==end)

{

if(f[mid]==-1)

{

f[mid]=element;

if(mid>last)

last=mid;

return;

}

else if(f[mid]<=element)

{

insert(f,element,mid+1);

return;

}

else

{

insert(f,element,mid);

return;

}

}

int m=mid;

while( m < end && f[m] == -1 )

m++;

if(m==end)

{

if(f[m]!=-1&&f[m]<=element)

insert(f,element,m+1);

else

find_place(f,element,start,mid);

}

else if(m==start)

{

if(f[m]>element)

insert(f,element,m);

else

find_place(f,element,m+1,end);

}

else

{

if(f[m]==element)

{

insert(f,element,m+1);

}

else if(f[m]>element)

{

find_place(f,element,start,m-1);

}

else

find_place(f,element,m+1,end);

}

}

//The main function :)

int main()

{

int i,j,k,n,e;

int *s,*f;

scanf("%d",&n); //Scan the number of elements.

s=(int *)malloc(sizeof(int)*n);

for(i=0;i<n;i++)

scanf("%d",&s[i]);

scanf("%d",&e); // Choose the gap size.

f=(int *)malloc((1+e)*n*sizeof(int));

for(i=0;i<(1+e)*n;i++)

f[i]=-1;

f[0]=s[0];

i=1;

last=0;

int inserted=1;

while( inserted < n )

{

k=inserted;

while(inserted < n && k--)

{

find_place(f,s[i],0,last);

inserted++;

i++;

}

balance(f,e,inserted);

}

for(i=0;i<(1+e)*n;i++)

if(f[i]>=0)

printf("%d ",f[i]);

printf("\n");

return 0;

}

</source>

===Python Implementation===

<source lang="python">

def library_sort(array, epsilon):

def binary_search(array, element, start, end):

mid = start + ((end-start)//2)

if start == end:

if array[mid] is not None and array[mid] <= element: return mid + 1

else: return mid

else:

m = mid

while m < end and array[m] is None: m += 1

if m == end:

if array[m] is not None and array[m] <= element: return m + 1

else: return binary_search(array, element, start, mid)

elif m == start:

if array[m] > element: return m

else: return binary_search(array, element, m+1, end)

else:

if array[m] == element: return m + 1

elif array[m] > element: return binary_search(array, element, start, m-1)

else: return binary_search(array, element, m+1, end)

def insert(array, element, index):

nonlocal last_insert_index

if array[index] is None:

array[index] = element

else:

while array[index] is not None:

array[index], element = element, array[index]

index += 1

array[index] = element

index += 1

if index > last_insert_index:

last_insert_index = index

def balance(array, num_spaces, total_inserted):

nonlocal last_insert_index

queue = [None] * len(array)

inserted = index = 1

top = bottom = 0

while inserted < total_inserted:

spaces = 0

while spaces < num_spaces:

if array[index] is not None:

queue[bottom] = array[index]

bottom += 1

array[index] = None

index += 1; spaces += 1

if array[index] is not None:

queue[bottom] = array[index]

bottom += 1

array[index] = queue[top]

index += 1; top += 1; inserted += 1

last_insert_index = index - 1

array_len = len(array)

copy = [None] * (1 + epsilon) * array_len

copy[0] = array[0]

last_insert_index = 0

inserted = index = 1

while inserted < array_len:

round_inserts = inserted

while inserted < array_len and round_inserts > 0:

insertion_index = binary_search(copy, array[index], 0, last_insert_index)

insert(copy, array[index], insertion_index)

round_inserts -= 1; inserted += 1; index += 1

balance(copy, epsilon, inserted)

return [x for x in copy if x is not None]

</source>

==Analysis=Pseudocode===

'''procedure''' rebalance(A, begin, end) '''is'''

[[Image:Library sort graph.png|Library sort runtime for decreasing sequences]]

r ← end

w ← end × 2

'''while''' r ≥ begin '''do'''

A[w] ← A[r]

A[w-1] ← gap

r ← r − 1

w ← w − 2

'''procedure''' sort(A) '''is'''

[[Image:Insertion sort graph.png|Insertion sort runtime for decreasing sequences]]

n ← length(A)

S ← new array of n gaps

'''for''' i ← 1 to floor(log2(n-1)) '''do'''

rebalance(S, 1, 2^(i-1))

'''for''' j ← 2^(i-1) to 2^i '''do'''

ins ← binarysearch(A[j], S, 2^i)

insert A[j] at S[ins]

Here, <code>binarysearch(el, A, k)</code> performs [[binary search]] in the first {{mvar|k}} elements of {{mvar|A}}, skipping over gaps, to find a place where to locate element {{mvar|el}}. Insertion should favor gaps over filled-in elements.

The two graphs show the performance of library sort and insertion sort for the same inputs. It is quite clear that library sort takes O(n log n) time approximately while the insertion sort takes O(n²) time.

== References ==

Line 296 ⟶ 67:

{{sorting}}

[[Category:Sorting algorithms]]

[[Category:Comparison sorts]]

[[Category:Stable sorts]]