• 作成:

アルゴリズムとデータ構造2(ソート(2))

ヒープの表現ってノード要素とポインタで表すのと, 配列で表現するのとどっちが良いんでしょうね.

まあ, どっちが絶対的に良いとかはなく, 挿入や削除が多ければポインタが良くて, あまり変わらず閲覧するだけなら配列が良いのでしょうが. 実際どれぐらい挿入することがあれば配列ではなくポインタが良くなるのでしょう. 何も考えずに配列の方が優位ってことが多すぎるんですよね.

実装の楽さはGCが無ければ配列のほうが楽で, GCがあればポインタの方が楽ですね. 永続性や普遍性を考えるとポインタのほうが圧倒的に楽.

挿入ソート, シェルソートの何が速いのかよくわからない, データが整列されたとき限定のアルゴリズムってことで良いんでしょうか.

計算量の比較が今ひとつわからない, O(n)O(n)O(nlogn)O(n \log n)は具体的にどういう風に違うのかパッとわからない.

wolframでグラフ描画してもらおうと思いました.

2つのグラフを描くにはplot n, n * log(n)と入力すれば良いことはわかりましたが, これを範囲指定する方法がわからない. plot n + 1, n * log(n), n = 0 to 100だと通るんですが, plot n, n * log(n), n = 0 to 100だと通らない…

plot y = n, y = n * log(n), n = 0 to 100だと通りました. wolframの文法の決まりがよくわかりません…

授業内問題

データ列6, 7, 8, 9, 10, 13, 12, 11, 3, 5, 4, 1, 2 をシェルソートする過程を書きなさい。但しh=6, 3, 1とする。

6, 7, 8, 9, 10, 13, 12, 11, 3, 5, 4, 1, 2 → 2, 7, 3, 5, 4, 1, 6, 11, 8, 9, 10, 13, 12 → 2, 4, 1, 5, 7, 3, 6, 10, 8, 9, 11, 13, 12 → 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

データ列 2, 5, 6, 3, 4, 1 をヒープソート、クイックソート(ピボットはデータ列の先頭から2つ見た大きい方を取る)でそれぞれソートする過程を書きなさい。

ヒープソート

2, 5, 6, 3, 4, 1 → 5, 2, 6, 3, 4, 1 → 6, 2, 5, 3, 4, 1 → 6, 3, 5, 2, 4, 1 → 6, 4, 5, 2, 3, 1 → 6, 4, 5, 2, 3, 1

ヒープ化完了.

6, 4, 5, 2, 3, 1 → 1, 4, 5, 2, 3, 6 → 4, 1, 5, 2, 3, 6 → 4, 2, 5, 1, 3, 6 → 3, 2, 5, 1, 4, 6 → 5, 2, 3, 1, 4, 6 → 1, 2, 3, 5, 4, 6 →

クイックソート

(2, 5, 6, 3, 4, 1) → (2, 1, 4, 3), (6, 5) → (1, (2, 4, 3)), (6, 5) → (1, (2, 3, 4)), (6, 5) → (1, ((2, 3), 4)), (6, 5) → 1, 2, 3, 4, (6, 5) → 1, 2, 3, 4, (5, 6) → 1, 2, 3, 4, 5, 6

クイックソートを実装することは出来るんですが, どうにも原理をいつも忘れてしまって, ダメになります. 私には実装して即座に忘却してしまう性質があります…