|
ins ← binarysearch(S[:2^(i-1)]
insert A[j] at S[ins]
===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>
== References ==
|
