リンクリストを使用したCの挿入ソート

Question

私は電話帳プログラムを作成する必要があります。プログラムはファイルから名前と番号を読み取る必要があります。私はこのデータを含むリンクリストを作成しました。今ではアルファベット順にソートしたいと思っています。私はどうしたらいいですか？

Answer 1

あなたの目的によって異なります。

これを効率的に実行するには、配列にすべての要素のポインタを置き、quicksort（Cではqsort）のようなアルゴリズムを使用して配列をアルファベット順にソートします。最後に、並べ替えられた配列からリストを再作成します。

一方、これが宿題で、投稿のタイトルが示すように挿入ソートを使用する必要がある場合は、別の問題です。

Answer 2

リンクリストを作成した後でソートしますか？

このようなデータをソートする最適な方法は、ツリーを使用してデータをロードするときにソートすることです。ハッシュがおそらく最速であるにもかかわらず、ツリーデータ構造も迅速に検索できます。 strcmpはソートや検索を行う最も簡単な方法ではないことに注意してください。検索タームにインデックスを維持して、インデックスが最初に一致しない文字を指すようにコーディングすることができます。それで、あなたはただ一つのキャラクターを比較する必要があります。しかし、私はそれのためのサンプルコードを与える時間がありません。

typedef struct directory_entry_t 
{ 
    char *name; 
    char *number; 
    directory_entry_t *before; 
    directory_entry_t *after; 
} directory_entry; 

... 

bool found; 

while(!found) 
{ 
    int result = strcmp("name", node->name); 

    if(0 == result) 
    { 
     fprintf(stderr, "Duplicate entry for %s.\n", name); 
    } 
    else if(0 < result) 
    { 
     if(NULL == node->after) 
     { 
      /* Create a new node, populate it, and store a pointer to it at node->after. */ 
      found = true; 
     } 
     else 
     { 
      node = node->after; 
     } 
    else 
    { 
     /* Like the above case, but for before. */ 
    } 
} 

Answer 3

挿入ソート遅いですが、あなたが使用したい場合には、（T & C適用）絶食そのうち、sorting algoritms他の多くのがありますがhttp://en.wikipedia.org/wiki/Insertion_sort

を見てO（NlogN）です。 quicksortまたはmerge sortのいずれかをお勧めします。

Answer 4

リンクリストは、並べ替えのための想像を絶する最悪のデータ構造です。挿入すると、リスト全体で線形トラバーサルを行う必要があります。正しい質問をしてもよろしいですか？

Answer 5

リンクリストをソートするには、挿入ソートやスタックベースのマージソルトの実装などのオンラインアルゴリズム（高速ランダムアクセスに依存しないアルゴリズム）が必要です。

既にソートされたリストに（少数の）アイテムを挿入する場合は、挿入ソートを使用します。完全なリストをソートする（または多数のアイテムを挿入する）場合は、mergesortを使用します。

これらのアルゴリズムの実装がここで見つけることができます：

• ll_sort.h
• ll_sort.c

コードが実際にテストされていないとして、あなたがバグを見つけた場合、私に知らせてください。