アルゴリズムとデータ構造

アルゴリズムと
データ構造
第10回
ソート（1）：単純なソートアルゴリズム
先週の復習
再帰の基本
再帰関数呼び出し
再帰呼出しを使うことのメリット
再帰的アルゴリズムの作り方
再帰呼出しの時間計算量
再帰関数の応用例
ハノイの塔
8王妃問題
先週の演習問題
解説 recur(-1) : （何も実行されない）
recur(0) : （何も実行されない）
recur(1) : recur(-1) 1 recur(0)
→
1
recur(2) : recur(0) 2 recur(1)
→
2 1
21
recur(3) : recur(1) 3 recur(2)
→
1321
1 3 21
recur(4) : recur(2) 4 recur(3)
→
21 4 1321
2141321
recur(5) : recur(3) 5 recur(4)
→
132152141321
1321 5 2141321
recur(6) : recur(4) 6 recur(5)
→
2141321
21413216132152141321
6 132152141321
答え：
ソート（整列、ソーティング、sorting）
本日の内容 
単純なソートアルゴリズム




比較によらないソート





バブルソート
挿入ソート
選択ソート
バケットソート
基数ソート
シェルソート
クイックソート
マージソート
ソートの基本


レコードの集まりを，キーの値の大小関係に従って
昇順（または降順）に並べかえる操作
ソートの対象は，複数の欄からなるレコード
氏名と身長欄か
ら成るレコード．
Cでは，構造体
を用いて記述
青木
小田
金子
佐藤
177
158
170
174
渡辺
170
身長をキーとして
降順にソート
青木
佐藤
金子
渡辺
177
174
170
170
小田
158
同じキーをもつレコードが
複数ある時は連続して並ぶ
昇順、降順

昇順(ascending order)



数値の場合、小さいものから大きいものへ
１，３，５，８，１０
文字列の場合、辞書式順序
a, aa, abc, g, zz, zzzz
降順(descending order)


数値の場合、大きいものから小さいものへ
１０，８，５，３，１
文字列の場合、辞書式順序の逆
zzzz, zz, g, abc, aa, a
ソートアルゴリズムの要件

計算量（時間的，空間的）

内部ソート／外部ソート


ランダムアクセス可能なメモリの利用を前提とする方式か
否か
安定／不安定

キーの値が同じデータを整列した場合に整列前の位置関
係が維持されるか
10, 3, 5, 3, 1 ⇒ 1, 3, 3, 5, 10 安定
10, 3, 5, 3, 1 ⇒ 1, 3, 3, 5, 10 不安定
内部ソートと外部ソート
主記憶
(メモリ)
ランダム
１
２
５
６
７
２
５
１
６
７
外部記憶
(磁気テープなど)
シーケンシャル
主記憶
(メモリ)
ランダム
整列したい
データ
２
５
１
６
７
主記憶にコピー
入りきらない
外部記憶
(磁気テープなど)
シーケンシャル
整列したい
データ
２
５
１
６
７
１０
４０
３
４
３５
安定なソート

同じキーをもつレコードが2つ以上ある場合に，整列
前の位置関係が整列後も保たれているアルゴリズム
を安定である(stable)という
５A ７４８５B ３２
安定なアルゴリズムによる整列結果
不安定なアルゴリズムによる整列結果
２３４５A ５B ７８
２３４５B ５A ７８
ソート（整列）アルゴリズムの分類
名称
計算量
内部/外
部
安定/不安定
バブルソート
O(n2)
内部
安定
挿入ソート
O(n2)
内部
安定
選択ソート
O(n2)
内部
不安定
バケットソート O(n)
内部
安定
データに制限
有
基数ソート
O(mn)
内部
安定
データに制限
有
シェルソート
O（n1.25）～
O（n1.5）
内部
不安定
クイックソート O(n log n)
内部
不安定
マージソート
外部
安定
O(n log n)
備考
最悪O(n2)
O(n2)とO(n log n)の比較

n が大きいとき，O(n2)とO(n log n)の差は顕著
例）

n = 32 = 25のとき
n2 = 210 = 1024
6.4倍
n log2 n = 32×log2 25 = 32×5 = 160
10
 n = 1024 = 2 のとき
100倍
n2 = 220 = 1048576 ≒ 100万
n log2 n = 1024×log2 210 = 1024×10 = 10240 ≒ 1万
バブルソート（bubble sort）
[1]
[2]
[3]
[4]
[5]
7
3
5
9
6
4
[n-1]
8
9
2
a [0]


別名：単純交換ソート
配列の後ろから先頭に向かって
スキャンし，隣り合う２つの要素の
大小関係が逆であったら入れか
える
2
2 8
9
バブルソートのコード
整数を昇順に並べる場合
void bubble_sort(int a[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++){
for (j = n - 1; j > i; j--){
if(a[j] < a[j-1])
a[j]とa[j-1]を交換;
}
}
}
i → a [0]
[1]
[2]
[3]
[4]
[5]
ｊ → [n-1]
バブルソートの実行例１
a[0] a[1]
6
1
1
6
4
a[6]
1
4
3
1
3
7
7
1
8
9
9
8
バブルソートの実行例２
a[0] a[1]
整列前
i＝0のあと
i＝1のあと
i＝2のあと
i＝3のあと
i＝4のあと
i＝5のあと
i＝6のあと
i＝7のあと
a[8]
９
３
２
１
４
７
５
５８
１
１
１
１
１
１
２
２
２
２
２
２
３
３
３
３
３
３
９
４
４
４
４
４
４
９
５
５
５
５
５
５
９
５
５
５
５
５
５
９
７
７
７
７
７
７
９
８
整列済 ←
８
８
８
８
８
９
バブルソートの実行例２
a[0] a[1]
整列前
i＝0のあと
i＝1のあと
i＝2のあと
i＝3のあと
i＝4のあと
i＝5のあと
i＝6のあと
i＝7のあと
９
１
１
１
１
１
１
１
１
３
９
２
２
２
２
２
２
２
a[8]
２
３
９
３
３
３
３
３
３
１
２
３
９
４
４
４
４
４
４
４
４
４
９
５
５
５
５
７
５
５
５
５
９
５
５
５
５
７
５
５
５
５
９
７
７
５
５
７
７
７
７
７
９
８
整列済 ←
８
８
８
８
８
８
８
８
９
バブルソートの実行例２
a[0] a[1]
整列前
i＝0のあと
i＝1のあと
i＝2のあと
i＝3のあと
i＝4のあと
i＝5のあと
i＝6のあと
i＝7のあと
９
１
１
１
１
１
１
１
１
３
９
２
２
２
２
２
２
２
a[8]
２
３
９
３
３
３
３
３
３
１
２
３
９
４
４
４
４
４
４
４
４
４
９
５
５
５
５
７
５
５
５
５
９
５
５
５
５
７
５
５
５
５
９
７
７
５
５
７
７
７
７
７
９
８
整列済 ←
安定なソート
８
８
８
８
８
８
８
８
９
問題1

次のデータをバブルソートで昇順に並べ替える経
過を示しなさい。
a[5] = {９,３,４,１,４};
i
j
初期状態
0
4
0
0
0
3
2
1
1
1
1
2
4
3
2
4
2
3
3
4
a[0]
９
a[1]
３
a[2]
４
a[3]
１
a[4]
４
i
j
初期状態
0
4
0
0
0
1
1
1
2
2
3
3
2
1
4
3
2
4
3
4
a[0]
９
９
a[1]
３
３
a[2]
４
４
a[3]
１
１
a[4]
４
４
９
９
１
１
１
１
１
１
１
３
１
９
９
９
３
３
３
３
１
３
３
３
３
９
９
４
４
４
４
４
４
４
４
４
９
４
４
４
４
４
４
４
４
４
９
バブルソートの計算量
i=0
a [0]
i=1
i のループ
n－1回
i=n-2
[1]
[2]
[3]
j:
n-1回
j:
n-2回
[n-1]
j:
1回
全体
O(n2)
n 1
比較：
 (n  k )  {n(n  1)}/ 2 ⇒ O(n2)
k 1
交換：（a[j]<a[j-1]）の個数: 逆順の場合、比較の回数分
交換も起こる ⇒ O(n2)
挿入ソート（insertion sort）


０〜(i-1)番目まではすでにソート済
ｉ番目の要素を０〜ｉの間の適切な位置に挿入する
ソート済
a
[0]
[1]
3
5
[n-1]
[i-1] [i]
8
10 11
7
1
3
実行例
6
1
4
3
4
7
9
8
8
挿入ソートのコード
void insertion_sort(int a[], int n)
{
int i, j;
for (i = 1;i < n; i++){
j = i;
while (j >= 1 && a[j] < a[j-1]){
a[j]とa[j-1]を交換;
j--;
}
}
ｊ >= 1を満たさな
いのでwhileルー
プを抜ける
a[0]
ｊ → i → [1]
[2]
[3]
[4]
}
[n-1]
3
2
3
2
1
4
挿入ソートのコード
void insertion_sort(int a[], int n)
{
int i, j;
for (i = 1;i < n; i++){
j = i;
while (j >= 1 && a[j] < a[j-1]){
a[j]とa[j-1]を交換;
j--;
}
}
ｊ >= 1を満たさな
いのでwhileルー
プを抜ける
a[0]
ｊ→
[1]
i → [2]
[3]
[4]
}
[n-1]
1
3
2
2
1
3
4
挿入ソートのコード
void insertion_sort(int a[], int n)
{
int i, j;
a[0]
[1]
[2]
ｊ → i → [3]
[4]
for (i = 1;i < n; i++){
j = i;
while (j >= 1 && a[j] < a[j-1]){
a[j]とa[j-1]を交換;
jは i ～ 1までの全て
j--;
について繰りかえし調
べるのではなく，適切な
}
挿入位置で止まる
}
}
[n-1]
1
3
2
3
1
2
1
3
4
番兵(Sentinel)


配列の範囲を超えないよう見張るために使用
決してa[j]とa[j-1]の交換が起きないような値
を入れておくことで，コードを簡略化できる
a
[0]
i
↓
[i-1] [i]
[1]
-∞ 3
5
8
10
1
← ｊ
番兵
[n-1] [n]
挿入ソートのコード２
a [0] -∞
番兵を使う場合
void insertion_sort(int a[], int n)
{
int i, j;
ｊ → [1]
i → [2]
[3]
[4]
[5]
a[0] = -∞;
for (i = 2;i <= n; i++){
j = i;
while (a[j] < a[j-1]){
a[j]とa[j-1]を交換;
j--;
}
}
}
必ずa[1]>a[0]
になり，ループを
脱出
[n]
2
3
2
3
1
4
挿入ソートの実行例
整列前
1回実行後
2回実行後
iの
ループ 3回実行後
4回実行後
5回実行後
6回実行後
7回実行後
8回実行後
４
５
５
７
８
１２
９
３
４
４
１
１
１
１
５
５
４
２
２
２
５
５
５
４
４
３
７
７
５
５
５
４
８
８
７
５
５
５
１
１
８
７
７
５
９
９
９
９
９
８
３
３
３
３
３
９
２
２
２
８
８
７
整列済 ←
挿入ソートの実行例
整列前
1回実行後
2回実行後
iの
ループ 3回実行後
4回実行後
5回実行後
6回実行後
7回実行後
8回実行後
４
４
４
４
４
１
１
１
１
５
５
５
５
５
４
２
２
２
５
５
５
５
５
５
４
４
３
７
７
７
７
７
５
５
５
４
８
８
８
８
８
７
５
５
５
１
１
１
１
１
８
７
７
５
２
２
２
２
２
２
８
８
７
９
９
９
９
９
９
９
９
８
３
３
３
３
３
３
３
３
９
整列済 ←
安定なソート
問題2

次のデータを挿入ソートで昇順に並べ替える
経過を示しなさい。
a[5] = {９,３,４,１,４};
i
j
初期状態
1
1
2
3
2
3
3
3
4
2
1
4
a[0]
a[1]
a[2]
a[3]
a[4]
９
３
４
１
４
i
j
初期状態
1
1
2
3
3
3
4
2
3
2
1
4
a[0]
９
３
a[1]
３
９
a[2]
４
４
a[3]
１
１
a[4]
４
４
３
３
３
１
１
４
４
１
３
３
９
１
４
４
４
１
９
９
９
４
４
４
４
４
９
挿入ソートの計算量
i のループ n－1回
i=2
i=3
i=4
i=n
a [0]
[1]
[2]
[3]
[n]
j
j のループは
適切な挿入位置
で止まる
内側（j）のループ回数
Min：0回
Max：i-1回
平均：約(i-1)/2回
n
比較：
全体
O(n2)
 (i 1) / 2  {n(n  1)}/ 4 ⇒O(n2)
i 2
交換：（a[j]<a[j-1]）の個数≦
{n(n  1)} / 4
⇒ O(n2)
選択ソート（selection sort）

整列されていない部分から最小要素を選び，先頭と
入れかえる処理を繰り返す
i (着目位置)
a
[0]
[1]
1
3
未ソート
[n-1]
5
9
10
入れかえ
7
20 17 18
整列されていない部分の最小値
選択ソート実行例
• 最小要素を選択し、それを先頭要素と交換
• 同様に次の最小要素を順次先頭側要素と交換
6
1
4
3
8
4
8
4
3
6
6
8
1
7
9
8
8
7
9
選択ソートのコード
void selection_sort(int a[], int n)
{
int i, j, lowest, lowkey;
for (i = 0;i < n - 1; i++){
lowest = i;
lowkey = a[i];
for (j = i + 1; j < n; j++){
if (a[j] < lowkey){
lowest = j;
lowkey = a[j];
}
}
a[i]とa[lowest]を交換;
}
}
a [0] 1
[1]
i → [2]
[3]
[4]
lowest→ [5]
ｊ → [n-1]
2
9
3
7
3
9
選択ソートの実行例
整列前
1回実行後
2回実行後
iの
ループ 3回実行後
4回実行後
5回実行後
6回実行後
7回実行後
8回実行後
９
３
４
９
７
２５
８
１
１
１
１
１
１
１
２
２
２
２
２
２
３
３
３
３
３
３
９
４
４
４
４
４
７
７
５
５
５
５
４
９
９
７
７
７
８
８
８
８
９
９
９
９
９
９
９
９
５
５
７
９
８
８
整列済 ←
選択ソートの実行例
整列前
1回実行後
2回実行後
iの
ループ 3回実行後
4回実行後
5回実行後
6回実行後
7回実行後
8回実行後
９
１
１
１
１
１
１
１
１
３
３
２
２
２
２
２
２
２
４
４
４
３
３
３
３
３
３
９
９
９
９
４
４
４
４
４
７
７
７
７
７
５
５
５
５
２
２
３
４
９
９
７
７
７
５
５
５
５
５
７
９
８
８
８
８
８
８
８
８
８
９
９
整列済 ←
不安定なソート
１
９
９
９
９
９
９
９
９
問題3

次のデータを選択ソートで昇順に並べ替える
経過を示しなさい。
a[7] = {９,３,２,１,４,８,７};
i
初期状態
０
1
2
3
4
5
a[0]
９
a[1]
３
a[2]
２
a[3]
１
a[4]
４
a[5]
８
a[6]
７
i
初期状態
a[0]
９
a[1]
３
a[2]
２
a[3]
１
a[4]
４
a[5]
８
a[6]
７
０
１
３
２
９
４
８
７
1
2
3
4
5
１
１
１
１
１
２
２
２
２
２
３
３
３
３
３
９
９
４
４
４
４
４
９
７
７
８
８
８
８
８
７
７
７
９
９
選択ソートの計算量
i のループ
n－1回
i=0
i=1
i=2
i=n-2
a [0]
[1]
[2]
[3]
j
j:
n-1回
j:
n-2回
j:
1回
[n-1]
n 1
比較：
 (n  k )  {n(n  1)}/ 2 ⇒
k 1
O(n2)
交換：各iの最後に1回→全体でn-1回 ⇒O(n)
全体
O(n2)
まとめ
全体の計算量
比較
交換
バブルソート
O(n2)
n(n-1)/2 回
（a[j]<a[j-1]）の
個数回
挿入ソート
O(n2)
約n(n-1)/4 回
（a[j]<a[j-1]）の
個数回
選択ソート
O(n2)
n(n-1)/2 回
n-1回
挿入ソートは，整列済みのデータに
新しいデータを追加してから並べかえるときなど，
ほぼ整列済みのデータのソートが得意
演習問題
演習問題
名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する
提出先：
工学部電子情報実験研究棟５階
NO.5506室のドアのポストに入れてください
締め切り時間：
来週月曜日（6月23日）午前９時まで

Download Report