Solved

Library Sort implementaion aka Gapped Insertion Sort implementation

Posted on 2007-11-16
4
1,950 Views
Last Modified: 2010-04-21
INSERTION SORT Is O(n log n) is the name of a paper by Michael A. Bender and others where they discuss an improvement to Insertion Sort by leaving gaps between insertions so that the list does not have to be moved each time a new item is inserted into the lower part of the list.

Wikipeadia calls this a Library Sort or a Gapped Insertion sort which is not at all the same idea as the gaps used with a shell sort.

Unfortunately, no code was included in the paper and i have seen no implementations of this Library sort.
I am sure that I can write my own but as I am lazy and busy, I won't be able to start work on this for a couple of weeks.

Anyone that either writes the code or posts an implementation of the algorithm in any popular language (ie.. C, C#, java, C++, Visual Basic, etc...) will get my grateful acknowledgement of their superior skills plus a cool 500 points. :)

thanks,

clays_dna
0
Comment
Question by:clays_dna
  • 3
4 Comments
 
LVL 55

Accepted Solution

by:
Jaime Olivares earned 500 total points
ID: 20303395
0
 

Author Comment

by:clays_dna
ID: 20306586
Accepting jamie's submission. It is in chineese but the guy at least seems to think he wrote a library sort. Will check it out thoroughly at a later time but did not want to hold up the points since this seems to be the only one published on the net. :)

thanks

clay
0
 

Author Comment

by:clays_dna
ID: 20306590
see code pasted from web site.
figured I should keep it all in one place
 基本算法连载(8)-Library Sort(gapped insertion sort)
 

特色:Library sort优于传统的插入排序(时间复杂度为O(n^2)),它的时间复杂度为O(nlogn),采用了空间换时间的策略。

思想:一个图书管理员需要按照字母顺序放置书本,当在书本之间留有一定空隙时,一本新书上架将无需移动随后的书本,可以直接插空隙。Library sort的思想就源于此。

实现:有n个元素待排序,这些元素被插入到拥有(1+e)n个元素的数组中。每次插入2^(i-1)个元素,总共需要插logn趟。这2^(i-1)个元素将被折半插入到已有的2^(i-1)个元素中。因此,插入i趟之后,已有2^i个元素插入数组中。此时,执行rebalance操作,原有处在(1+ e)2^i个位置的元素将被扩展到(2+2e)2^i个位置。这样,在做插入时,由于存在gap,因此在gap未满之前无需移动元素。

具体代码:
 
 

/*

* length:待排序元素个数

* elements:待排序数组

* factor:常数因子

*/

void librarySort(int length,float factor,int elements[]){

 int i,j;

 //扩展后的数组长度

 int expandedLen = (int)((1+factor)*length);

 int* orderedElem = (int*) malloc(expandedLen*sizeof(int));

  

 //标志gap

 int flag = 1<<31;

 for(i=0;i<expandedLen;i++){

  orderedElem[i] = flag;

 }

 

 int index = 1;

 int numOfIntercalatedElem = 1;

 orderedElem[0] = elements[0];

  

 while(length>numOfIntercalatedElem){

  //第i次插入2^(i-1)个元素

  for(j=0;j<numOfIntercalatedElem;j++){

   //待插入元素为elements[index]   

   //------------折半插入---------------

   int mid;

   int low = 0;

   int high = 2 * numOfIntercalatedElem - 1;

   while(low <= high){

    mid = (low + high)/2;

    

    int savedMid = mid;

    //如果mid所在位置为gap

    while(orderedElem[mid] == flag){     

     if(mid == high){

      //当向右遍历没有找到元素值时,改成向左遍历

      mid = savedMid - 1;

      while(orderedElem[mid] == flag){

       mid--;

      }

      break;

     }

     mid++;

    }

    

    if(elements[index] > orderedElem[mid]){

     low = mid + 1;

     //缩小范围

     while(orderedElem[low] == flag){

      low = low+1;

     }

    }else{

     high = mid - 1;

    }

   }   

   

   //把elements[index]插入到orderedElem[high+1]

   //当位置为空,没有存储元素值时...

   if(orderedElem[high+1] == flag){

    orderedElem[high+1] = elements[index];

   }else{

    //位置非空,首先往前挪动元素,如果前面已满,向后挪动元素

    int temp = high+1;

    while(orderedElem[temp] != flag){

     temp--;

     if(temp < 0){

      temp = high+1;

      break;

     }

    }     

    

    //向后移动 

    while(orderedElem[temp] !=flag){

     temp++;

    }     

     

    while(temp < high){

     orderedElem[temp] = orderedElem[temp+1];

     temp++;

    }

     

    while(temp > high+1){

     orderedElem[temp] = orderedElem[temp-1];

     temp--;

    }   

     

    orderedElem[temp] = elements[index];          

   }

   //--------------------------------- 

   index++;

   if(index == length){

    break;

   } 

  }

  

  numOfIntercalatedElem *=2;

  int generatedIndex;

  //Rebalance...

  for(j=numOfIntercalatedElem;j>0;j--){

   if(orderedElem[j] == flag){

    continue;

   }

   //原数组元素从i处移到2i处

   generatedIndex = j*2;

   if(generatedIndex >= expandedLen){    

    generatedIndex = expandedLen - 1;

    if(orderedElem[generatedIndex] != flag){

     break;

    }

   }   

   orderedElem[generatedIndex] = orderedElem[j];

   orderedElem[j] = flag;

  }     

 }

 //测试输出

 for(i=0;i<expandedLen;i++){

  printf("%d\n",orderedElem[i]);

 }

 

}

Open in new window

0
 

Author Closing Comment

by:clays_dna
ID: 31409706
Dont know if solution is complete or accurate because I cannot read the comments in Chinese. The chinese guy certainly thinks this is an implementation of the library sort. I wont know for sure till I trace thru it all and figure out what it is doing. Looks about right though from first glance.
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now