整列（ソート）とは
- データのリストを線形順序で並べ替える
- 昇順、降順
- 並べ替えの対象は「キーを含むレコード」
- レコード：データの構成単位
- キー：レコードの中で順序比較の対象となる欄
- 例：アドレス帳
- レコード：一人分の住所録情報（氏名、住所、電話番号）
- キー：氏名（フリガナ）
内部ソートと外部ソート
- 内部整列：整列の対象が主記憶に収まる
- 外部整列：二次記憶（ディスク等）を使う
安定ソート
- 同じキーをもつレコードの順序を保存するソートアルゴリズム
ソートのための三大要素
- 交換
- 選択
- 挿入
ほとんどのソートアルゴリズムは、これらの考え方を応用したもの
「交換」のサンプルコード（c言語）
swap.c
# include<stdio.h>
/* 値を交換する関数 */
void swap (int *x, int *y) {
int temp; // 値を一時的に保存する変数
temp = *x;
*x = *y;
*y = temp;
}
int main (void) {
int a = 1;
int b = 5;
printf("a = %d, b = %d\n", a, b);
swap(&a, &b);
printf("a = %d, b = %d\n", a, b);
return 0;
}
実行結果
a = 1, b = 5
a = 5, b = 1
代表的なソートアルゴリズム
選択ソート
挿入ソート
バブルソート
シェルソート
クイックソート
ヒープソート
基数ソート
マージソート
分布数え上げソート
参考
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜
ソートアルゴリズム20種をCで作ってみた
【Unity】ソートアルゴリズム12種を可視化してみた