ソートアルゴリズム(8)
今回はストランドソートを解説します。
ストランドソートは前回解説したマージソートと同じマージ系と呼ばれるソートアルゴリズムです。
マージソートではソートされていないリストを2分割してマージソートを再帰呼び出しして、ソートされたサブリストをマージするアルゴリズムでした。
ストランドソートでは、リストからソートされたサブリストを抽出し、結果リストにマージしていくことでソートします。
2009年12月15日 | カテゴリー:アルゴリズム
今回はストランドソートを解説します。
ストランドソートは前回解説したマージソートと同じマージ系と呼ばれるソートアルゴリズムです。
マージソートではソートされていないリストを2分割してマージソートを再帰呼び出しして、ソートされたサブリストをマージするアルゴリズムでした。
ストランドソートでは、リストからソートされたサブリストを抽出し、結果リストにマージしていくことでソートします。
2009年12月15日 | カテゴリー:アルゴリズム
今回はマージソートです。
マージソートの処理は
1.ソートするリストを2つに分ける
2.分けたリストをソートする
3.2つのリストをマージする
の3つの処理を再帰的に行うことでソートします。
1. のソートするリストの要素が0か1の場合にはソートする必要が無いのでリストをそのまま返します。これにより処理2で無限再帰しないことが保障されます。
2. の分けたリストをソートする部分でマージソートを再帰呼び出しします。
3. のマージでは2つのリストのそれぞれの先頭の値を比較し小さい(または大きい)方の値を取り出して結果のリストに追加します。
2009年12月1日 | カテゴリー:アルゴリズム
今回はヒープソートを紹介します。
ヒープソートとはその名のとおり、ヒープ構造を用いてソートを行うアルゴリズムです。
ヒープ構造とは2分木構造の一種で、ルートが常にそのヒープ構造の中の最大値(あるいは最小値)を指すように調整を行うデータ構造です。
このヒープ構造にソートを行いたいデータを追加していき、次にルートからデータを取り出して順番に並べていきます。
2009年11月17日 | カテゴリー:アルゴリズム