広く知られているinsertion sortのコードは駄目すぎる

insertion sortは「挿入ソート」と訳される。(Wikipedia→ http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 )

■　日本語版

Wikipediaの日本語のページのコードを引用すると次のようになっている。

for (i = 1; i < n; i++) {
    tmp = data[i];
    for (j = i; j > 0 && data[j-1] > tmp; j--) {
        data[j] = data[j-1];
    }
    data[j] = tmp;
}

上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味において(速度的な観点からすれば)とても無駄なコードである。

write backすることの弊害は、このコードでは読み出したばかりのところに書き出すだけなので、そのメモリは(いまどきのアーキテクチャなら)L1 cacheに載っているだろうから、大きな損だとは言えないが、例えば、t[X].Order に従って t[X] 自体を昇順ソートしたいような場合、write backのコストが馬鹿にならない。(sizeof(T[X])==12ぐらいだとして)

どこの馬鹿なアルゴリズムの教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。

■　英語版・イタリア語版

次いでWikipediaのinsertion sortの英語で書かれたページのコードも見ておこう。

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while j >= 0 and A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end;
        A[j + 1] := value;
    end;
end;

こちらはPascalで書かれている。さきほどのコードの変形だが、さきほどのコードよりさらに悪い。jにi-1を入れているが、これが無駄で、j にはｉを入れて、"j + 1 "を"j"に、" j "を "j - 1"にしたほうがコンパイラはいいコードを生成するだろう。

j >= 0の判定も初回は不要なわけで、insertの必要がない場合でも1回無駄な j >= 0の判定が必要になる。これもダメダメなコードと言える。

■　フランス語版

同じく、フランス語のほうも見てみよう。

#define MAX 100
 
void insertion(int t[MAX]) 
{
    /* Tri du tableau t par insertion sequentielle */
    int i,p,j;
    int x;
 
    for (i = 1; i < MAX; i++) 
    {
        /* Stockage de la valeur en i */
        x = t[i]; 
 
        /* Recherche du plus grand indice p inferieur a i tel que t[p] <= t[i] */
        p = i-1;
        while (t[p] > x && p-- > 0) {}
 
        /* Il faut inserer t[i] juste apres cette case */
        p++;
 
        /* Decalage avant des valeurs de t entre p et i */         
        for (j = i-1; j >= p; j--) {
            t[j+1] = t[j]; 
        }   
 
        t[p] = x; /* Insertion de la valeur stockee a la place vacante */
    }
}

こちらは、英語版のページに書かれていたコードをCで書き直したものだ。ループカウンタのj以外に、無駄なpという変数が導入されている。insertする地点pを求めて、そこ以降の要素をひとつ前にずらすコードなのだが、無駄な変数pが必要になる上に、そのあとのループではループカウンタをダウンカウントして、配列の後ろから前に向かってアクセスしている。

せっかくinsertする地点が求まっているのにわざわざreverse memory copyで書いて、コンパイラの最適化を阻害し、かつメモリハザードを起こす意味がわからない。こんなことは馬鹿のすることだ。

■　ドイツ語版

INSERTIONSORT(A)
1 for j = 2 to length(A)
2     do key = A[j]
          //Fuge A[j] ein in die sortierte Folge A[1 .. j - 1]
3         i = j - 1
4         while i > 0 and A[i] > key
5             do A[i + 1] = A[i]
6                 i = i - 1
7         A[i + 1] = key

Fortranで書かれた疑似コードなのでjのindexが2から始まるが、アルゴリズムとしては英語版と同じだ。これも話にならない。

■　中文

void insertion_sort(char array[], unsigned int first, unsigned int last)
 {
 	int i,j;
 	int temp;
 	for (i = first+1; i<=last;i++)
 	{
 		temp = array[i];
 		j=i-1;
 
 		//与已排序的数逐一比?，大于temp?，?数移后
 		while((j>=first) && (array[j] > temp))
 		{
 			array[j+1] = array[j];	
 			j--;
 		}
 
 		array[j+1] = temp;	
 	}
 }
這個更好:
 void InsertSort(char array[],unsigned int n)
 {
    int i,j;
    int temp;
    for(i=1;i<n;i++)
    {
      temp = array[i];//store the original sorted array in temp
      for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
      {
          array[j]=array[j-1];//all larger elements are moved one pot to the right
      }
     array[j]=temp;
    }
 }

中段に書いてある「這個更好」は、「以下のように書いたほうがいいよ」の意味だと思う。

前者は英語版のコード、後者は日本語版のコードとほぼ同じだ。さきほど私が解説したように後者のほうがいいコードが生成されるだろう。しかし、ループの最後でwrite backしているのはいただけない。

■　誰がこんな駄目なコードを広めたのか

以上で見てきたようにWikipediaのinsertion sortのサンプルはひどすぎる。おそらく書籍か何かの丸写しで、これがinsertion sortとして広く信じられているコードなんだろうけど、だとしたらとても悪いコードが広まっていると言わざるを得ない。

insertion sortは配列の要素が少ないときや、ある程度整順されていることがわかっているときにはとても有用なアルゴリズムであり、この関数の高速化はとても重要なのだ。(高速化が不要ならそもそも何も考えずに最初から言語ライブラリにあるqsort関数でも呼び出しておけばいいわけだし)

ひょっとしてinsertion sortを提案した奴(誰かは知らん)が、こんなひどいコードを広めたのかも知れない。だとしたらそいつはかなり罪深いと思う。

例えば、Introduction to Algorithms, Second Editionを見てみると(第3版は最近出たようだが私は持っていない)、次のコードが掲載されている。

INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[j]
3 	> Insert A[j] into the sorted sequence A[1 .. j - 1].
4 	i ← j - 1
5 	while i > 0 and A[i] > key
6 		do A[i + 1] ← A[i]
7 			i ← i - 1
8 	A[i + 1] ← key

Wikipediaの英語版のコードと同じアルゴリズムだ。一連の劣悪なコードはこいつが犯人かも知れない。

また、アルゴリズム本で有名なROBERT SEDGEWICKの著書の何冊かには次のコードが掲載されている。

procedure insertion;
    var i, j, v: integer;
    begin
    for i:=2 to N do
        begin
        v:=a[i]; j:=i;
            while a[j-1]>v do
                begin a[j] :=a[j-1]; j:=j-1 end;
            a[j] :=v
        end ;
    end ;

こちらはWikipediaの日本語版のコードとほぼ同じだ。こちらのコードはまだ救いはあるが、お世辞にも高速とは言い難い。ついでに言えば、このコードだけ見ればwhileのところの条件式に「j > 1 &&」が忘れてあるように思えるが、a[0]には番兵を置くと本文中にある。

■　まとめ

結局、insertion sortは最初に発案した奴が、きっとこんな駄目なコードを書いたんじゃないかと思う。(よく知らん)　そしてそれがほとんどすべてのアルゴリズムの教科書で採用されている。Wikipediaのinsertion sortは言わずもがなである。

私ならinsertion sortは次のように書く。これは、上で見てきたinsertionコードより典型的には3割程度速い。何より無駄なwrite backや"j = i - 1"などをしていないのでコードがわかりやすい。

  // yaneurao's insertion sort
  for (int i = 1; i < MAX; i++) 
  {
    int tmp = t[i];
    if (t[i-1] > tmp)
    {
      int j = i;
      do {
        t[j] = t[j-1];
        --j;
      } while ( j > 0 && t[j-1] > tmp);
      t[j] = tmp;
    }
  }

※ whileの条件を (t[j] > tmp && j > 0) と 書き間違えてました。コメント欄でご指摘をいただいたので修正しました。

また、昇順ではなく降順ならば、配列の要素をひとつ多く確保して、先頭にINT_MAXか、その末尾の要素にINT_MINを番兵(sentinel)として入れておき、jの終端チェックを省略することでさらに数割速くなるだろう。

昇順ソートの場合もt[0]は事前に空けておき、t[0] = INT_MINなどを番兵として代入しておき、j > 0 を省略することで同じく数割速くなるだろう。