明解 Javaによるアルゴリズムとデータ構造 6-1_ソートとは

6-1 ソートとは

安定性

• 安定 stable
  • 同一キーを持つ要素の順序関係が、ソート前後で必ず維持される
• 不安定
  • 同一キーを持つ要素の順序関係が、ソート前後で維持されるとは限らない

ソートの種類

• 内部ソート
  • ソート対象データが、1配列上に展開可能な場合に用いるアルゴリズム
• 外部ソート
  • ソート対象データが大量で、一度で処理しきれない場合のアルゴリズム

ソートの考え方

• ソートアルゴリズムの3大要素
  1. 交換
  2. 選択
  3. 挿入

明解 Javaによるアルゴリズムとデータ構造