概念と仕組み
ソートとは、与えられた順序に従ってデータを並べ替えるプロセスです。バブルソートは隣接する要素を比較し、マージソートは分割されたリストを結合する構造を利用します。
アルゴリズムの反復構造は、入力サイズが大きくなるにつれて、作業量が増加する度合いを決定します。同じサイズの入力でも、アルゴリズムの初期の順序や終了条件の変更が、結果を変化させる可能性があります。
関係式と成立条件
典型的なバブルソートの比較的規模はO(n²)、マージソートの規模はO(n log n)です。重要なことは、具体的な比較回数と、指数表記のOは異なるということです。
この実験は、コンピュータの実際の時間を測定するために、値の比較、交換、および書き込みの数を数えるという基準ではありません。また、データの書き込みと位置の交換を同じ操作とは扱いません。
仮想実験で読み取る変化
比較回数はデータ数、初期順序、手法で変わります。
実行時間ではなく値の比較と交換を数えます。マージの書き込みは別です。
重要な関係式と記号
bubble: n(n−1)/2 · merge: O(n log₂n)
| 記号 | 意味 | 単位 |
|---|---|---|
| n | 入力データ数 | 個 |
| O(n log n) | 入力サイズに応じた、漸近的成長の上限表現。 | 計算量 |
例で確かめる
マージの書き込みと交換は同じ操作ですか？
別の操作です · 比較回数はデータ数、初期順序、手法で変わります。
よくある誤解
- 比較の回数が少ないという事実は、すべてのコンピュータおよび入力が、時間において同じ割合で短縮されることを意味するわけではありません。