静的チェーンテーブル挿入ソート(List Insertion Sort)アルゴリズム

静的チェーンテーブル挿入ソート(List Insertion Sort)アルゴリズムは、直接挿入ソートの変種である.その改良の目的は,直接挿入並べ替えにおける移動回数を減らすことである(もちろん,この改良は複雑さを低減するものではなく,O(n^2)),従って、元の入力データに基づいて静的チェーンテーブルが付加される(空間の消費を低減するために、静的チェーンテーブルは実際には等長の下付き配列linkでシミュレートされ、等長の動的チェーン構造を構築する必要はない).このアルゴリズムの欠点は,移動回数を減らすが,等長のlink配列を1つ増やす必要があるため,空間で時間を取り替える方法でもある.
入力配列をv[]とし、昇順に並べた状態で静的チェーンテーブルlink[]のある位置iの要素値をx=v[i]とすると、link[i]は、その要素xの次のそれより大きい要素y=v[j]の位置値j、すなわちlink[i]=jを格納する.新しい要素z=v[i]を左のsorted listに挿入するたびに、左の順序付けされたサブシーケンスのhead位置から比較が開始されます(以下の実装では、headは必ずしも最初の要素を指すわけではありません!)、linkの下付きスケール値を探して、ある要素の値v[curr]が(アルゴリズムの安定性を保証するために、以上でなければならない)zより大きいまで、このときcurrポインタの前の位置ポインタはnextであり、zからnextとcurrの間に挿入するには、nextがzを指し、zがcurrを指すように修正する必要があります.sorted listの右端の要素のポインタ値はtailフラグとして-1になります.
得られた静的チェーンテーブルはkey値を直接格納した配列のようにランダムにアクセスできないため、List Insertion Sortの最後にlink[]に従ってv[]を昇順の静的配列(ここでの静的配列の要素はkey値)に変換する必要がある.変換方法はin-place方式を採用し,開放的な空間を必要としない.具体的にはheadからlinkの下付きスケール値を探し、見つかったkey値は左のサブ配列の一番右の要素と交換される(ここでサブ配列はすでに昇順の静的配列である).例えば、左のサブ配列の一番右の要素をi=2、v[i]=30、link[i]=5、見つかったkey値の下にcurr=6、v[curr]=20、link[curr]=7とすると、交換後v[i]=20、link[i]=6(注意は7ではありません!)、v[curr]=30、link[curr]=5、ここでlink[i]=6は、以降の操作「元の2番目の位置の要素が6番目の位置に移動した」ことを伝えるとともに、交換前のnext=link[curr]=7ポインタ、すなわち次の操作であるkey位置値currをメモすることを忘れないでください.
Javaバージョンの実装:

/**
 * 
 * List Insertion Sort algorithm 
 * (Adapted from http://en.wikipedia.org/wiki/Insertion_sort)
 *  
 *  
 * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/)
 * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php) 
 * 
 * @author ljs
 * 2011-07-20
 *
 */
public class ListInsertionSort {
    public static void sort(int[] v){
    	int n = v.length;
    	
    	//step 1: link[] creation
    	int[] link = new int[n];
    	int head=0;
    	int next=0,curr=0;
    	link[0] = -1;
    	for(int i=1;i<n;i++){
    		if(v[head]>v[i]){ //case: head is changed to i
    			link[i] = head;
    			head = i; //change head
    		}else{ 
    			//two stop cases:
    			//curr == -1: when we reach the tail 
    			//v[curr] > v[i]: insert i before curr, next is the predecessor of curr
    			//note: this loop executes at least once so 'next' always have valid value
    			for (curr = head ; curr != -1 && v[curr] <= v[i]; curr = link[curr])  
                    next =curr;  
    			//insert i between next and curr (also applicable to tail case when curr=-1)
    			link[next] = i;  
    			link[i] = curr;  
    		}
    	}
    	
    	//step 2: arrange v[] by link[] information: find curr and swap it with i
    	curr = head; //to scan linked list, always start with head 
    	//note the difference:
    	//in this step: between iterations, curr doesn't start with head at the beginning
    	//the link creation step: between iterations, we always scan from curr=head to find the insert position
        for (int i=0 ;i<n;i++){          	
            while(curr < i)  
                 curr = link [curr]; //look only those elements on the right side of current element
            
            next = link[curr]; //save for next iteration's start position 
            if (curr != i) {  //if curr==i, no need change since position i is done.
                int swap = v[i];  //swap key  
                v[i] = v[curr];  
                v[curr] = swap;  
                
                link[curr] = link[i];  //copy i's link  
                link[i] = curr;  //reset pointer link[i] for redirection
            }  
            curr = next;  //next iteration we start from 'next'
        }  
        
        //link[] is now useless, let it be garbage collected.   
    }
	 
	public static void main(String[] args) {
		 int[] v = {49,38,65,97,76,13,27,49};
		 ListInsertionSort.sort(v);
		 
		 for(int key:v){
			 System.out.format(" %d",key);
		 }
	}

}

Cバージョンの実装:(Wikipediaのコードを少し変更します:http://en.wikipedia.org/wiki/Insertion_sort)

#include <stdio.h>
#include <stdlib.h>

void ListinsertSort(int * v, int n)
 {
	int * link = (int *)malloc(sizeof(int)*n);
	int head =0;
	int  next,cur,i;
	link[0] = -1;
	//generate sorted static list: after sorting, head may not be the first element
	for (i = 1 ; i < n; i++){
		   if (v[head] > v[i]){
			   link[i] = head;
			   head = i;
			} else {
				   for (cur = head ; cur != -1 && v[cur] <= v[i]; cur = link[cur])
						  next =cur;
				   link[next] = i;
				   link[i] = cur;
			}
	}
	cur = head; //start with head
	for ( i = 0 ;i < n;i++){
		while(cur < i)
			 cur = link [cur]; //look only those elements on the right side of current element
		next = link[cur]; //save for next iteration
		if (cur != i) {
			int swap = v[i];  //swap key
			v[i] = v[cur];
			v[cur] = swap;
			link[cur] = link[i];  //swap link
			link[i] = cur;
		}
		cur = next;
	}
	free(link);
 }

int main(void) {
	int i;
	int* v = (int *)malloc(sizeof(int)*5);
	v[0]=3;v[1]=2;v[2]=1;v[3]=0;v[4]=5;

	ListinsertSort(v, 5);

	for(i=0;i<5;i++){
	    printf(" %d",v[i]);
	}
	free(v);
    return 0;
}