ソートアルゴリズム
ソートとは?
複数のデータを,ある特定の規則に従って並べ替えること.整列とも言う.ソートはExcelでよく目にするように,コンピュータでデータ処理する際にもっ とも使われる機能である.
- 昇順 ・・・ 小さいものから大きいものへ
- 降順 ・・・ 大きいものから小さいもの
代表的なソートの種類
バブルソート(単純交換ソート)
- 隣同士のデータの大小を比較
- もし,右が小さければ交換
- ポ インタを1つ左にずらす(「原列」の左端まで続ける)
単 純選択ソート
- 「原列」から一番小さいデータを探す
- 見つけた ら,「目的列」の右端に挿入
単純挿入 ソート(シャトルソート)
- 「原列」にあるデータを「目的列」の適切な位置へ挿入する
ク イックソート
- 高速なソートアルゴリズムの1つ。
- 枢軸となる値を決定し、その値より大きいデータ、小さ いデータに分けていく。
- → 詳細
ヒープソート
- ヒープ:親>子の構造を持つ2分木
- ヒープ構造の2分木の考え方を応用
- 配列構造で2分木を表現
- 詳細
用語の注意事項
ソート対象の配列を「目的列」「原列」のと表現することがあります.
- 目的列 ・・・ 並び変えた最終の列
- 原列 ・・・ 元の列
つまり,初期状態ではすべてのデータは「原列」で列の左側からだんだんと目的列になっていくと考えればよい.(最終的には,すべての データが目的列になる)