はじめての C

「リンクリスト 8」

リンクを ソートするのは 楽しい課題です。そこで 基本的な ソートの実装については、読者に 残しておくことにしましょう。

詳細な ソートの説明を するつもりは ありません。というのも、この tutorial が リンクリストについての ものだからです。ここでは、私の 小さな リストライブラリにある マージソートを 取り上げてみます。

(プログラムは 省略)

マージソートの アルゴリズムは、リンクリストであっても、変わりは ありません。ですので、どんな アルゴリズムの本を 開いても、そこには このコード そのままの やり方が 見つかるでしょう。

マージソートは、NlogN time での 実行が 保証され、また 安定性に 強い、よくできた 汎用の ソートアルゴリズムです。

競争相手である クイックソートや ヒープソートでは、一番の 決定的要素としての 安定性を 欠いているのです。

リンクリストを ソートする 他の 代わりとなる やり方は、初めのうちは、明らかでは ありません。しかし 二分木 - binary tree - では、いつでも この ソートするという 事実を 活用します。

単に リストを 渡っていくのであれば、最初の 項目を 削除して、二分木に 挿入します。このとき、規則に 則って tree を たどっていき、新しい リストの 末端へと 挿入していくのです。

人が やらせようと することとは 関係なく、たびたび、構造体の間での 交換 - switch - が 意味を もつことが あります。

この続きは、次の トピックで ...

最後の ところが よく わからない。誤訳かも ?
(追記) 一部 訳文を訂正。