クヌースリストの挿入方法は、C

Question

に私はソートを通じて読んでいるとドナルド・クヌース、第2版でコンピュータプログラミングのアートの3巻でアルゴリズムを検索します。 Knuthは、95ページの「リスト挿入」（従来の挿入ソートの変更）というアルゴリズムを紹介しました。

このページでは、「まっすぐな挿入のための正しいデータ構造は、リンクされた割り当て（セクション2.2.3）は、少数のリンクだけを変更する必要があるため、挿入には理想的です。 "しかし、97ページのMIXALプログラム（プログラムL）は、従来のリンクされた線形リスト構造（アドレスによってリンクされた一連のノード）を利用するようには見えません。代わりに、キーとリンクは構造体のような構造で一緒に格納され、これらの構造体はINPUTという配列に格納されているようです。

私はリファレンスとして、アルゴリズムのKnuthの説明、およびMIXALアセンブリ言語での彼の実装を提供してきたC.で、このアルゴリズムを実装しようとすることを決めました。私はキーがdata配列内の要素、それ自身、であるとすることを決めた、と私はlinksと呼ばれる並列のような配列内のリンクを置きます。 links配列のサイズがdata配列のサイズよりも大きいので、私は 'parallel-like array'と言っています。私はlinks配列の最初の要素として配列を格納することによって、data配列の最小要素のインデックスを簡単に決定できるように、これを行いました。なぜならlinksでこの余分なインデックス、インデックス0からlinks配列のN - （Nは - 1）dataアレイのインデックス1に対応します。 links配列の各要素は、並べ替えられたリストの次の要素の配列dataのインデックスに対応します。

私の質問は、これは、このアルゴリズムは、彼の説明に基づいて実施されることになっている、または私は何かが足りないのですかあるのですか？

int *listInsertion(int data[], int n) { 

    if (n > 1) { 
     int i, j, entry; 
     int *links = (int *) calloc(n + 1, sizeof *links); 
     links[n] = -1; 
     links[n - 1] = n - 1; 

     for (i = n - 2; i >= 0; i--) { 
      entry = data[i]; 
      for (j = i + 1; links[j] >= 0 && entry > data[links[j]]; 
        j = links[j] + 1) 
       continue; 

      if (j == i + 1) { 
       links[i] = i; 
      } else { 
       links[i] = links[i + 1]; 
       links[i + 1] = links[j]; 
       links[j] = i; 
      } 
     } 
     return links; 
    } 
    return NULL; 
} 

Answer 1

私は、あなたが最初にクヌース言及シンボルでアルゴリズムを実装して示唆しています。
これは、最初のバージョンをすぐに把握するのに役立ちます。

void insertSort(const int *K, int *L, int n) { 
    if (n == 1) return; 

    L[n] = n-1; 
    L[n-1] = n; 

    for (int j = n-2; j >= 0; j--) { 
    int entry = K[j]; 
    int p = L[n]; 
    int q = n; 

    while(entry > K[p]) { 
     q = p; 
     p = L[q]; 
     if (p == n) { 
     break; 
     } 
    } 

    L[q] = j; 
    L[j] = p; 
    } 
} 

次に、最初のバージョンをリファクタリングして機能強化したり、短くしたりすることができます。