ソートのプログラムの流れ
扱う問題： n個の整数を小さい順に並べる
n個の整数を入力、配列
a[1],a[2],…a[n]に入れる
91 28 36 77 51 11
最も手間のかかる部分
配列の中身を小さい
順に並び替える
11 28 36 51 77 91
よいアルゴリズムの必要性
a[1],a[2],…a[n]の値を
順に出力する
11 28 36 51 77 91
ソートアルゴリズムの種類
• 選択ソート (selection sort)
• バブルソート (bubble sort) 今回の授業
• 挿入ソート (insertion sort) で説明
• クイックソート (quick sort)
• マージソート (merge sort)
などなど
選択ソート(selection sort) ― その１
37 61 29 12 95 55
min
=
a[min] =
1
37
1 3 4
37 29 12
4
12
4
12
12 61 73 37 95 55
a[1], …,a[6] の
中から最小値
a[min]を見つける
a[1] とa[min]を交換
選択ソート ― その２
12 61 29 37 95 55
a[2], …,a[6] の
中から最小値
a[min]を見つける
12 29 61 37 95 55
a[2] とa[min]を交換
選択ソート ― その３
12 29 61 37 95 55
a[3],…,a[6]の中での最小値
を見つけa[3]と交換
12 29 37 61 95 55
a[4],…,a[6]の中での最小値
を見つけa[4]と交換
12 29 37 55 95 61
a[5],a[6]の中での最小値を
見つけa[5]と交換
12 29 37 55 61 95
ソート完了
バブルソート(bubble sort) ― その１
ソートの目的：a[1]≦a[2]≦・ ・ ・ ≦a[n-1]≦a[n]
基本操作： a[i] > a[i+1] ⇒ 中身を交換
37 61 29 12 95 55
a[5] > [6]
37 61 29 12 55 95
a[5] とa[6]を交換
バブルソート ― その２
37 61 29 12 55 95
a[4] ≦ [5] なのでそのまま
37 61 29 12 55 95
a[3] > [4] なので交換
37 61 12 29 55 95
a[2] > [3] なので交換
37 12 61 29 55 95
a[1] > [2] なので交換
12 37 61 29 55 95
a[1] =12は最小値！
バブルソート ― その３
12 37 61 29 55 95
12 29 37 61 55 95
12 37 61 29 55 95
12 29 37 61 55 95
交換
12 37 61 29 55 95
12 29 37 55 61 95
交換
12 37 29 61 55 95
交換
12 29 37 61 55 95
a[2]=29は２番目に小さい値
12 29 37 55 61 95
a[3]=37は3番目に小さい値
バブルソート ― その４
12 29 37 55 61 95
12 29 37 55 61 95
12 29 37 55 61 95
12 29 37 55 61 95
12 29 37 55 61 95
a[5]=61は5番目に小さい値
a[6]=95は6番目に小さい値
a[4]=55は4番目に小さい値
挿入ソート(insertion sort) ― その１
37 91 15 24 86 55
a[1], a[2]をソート
37 91 15 24 86 55
a[1],…, a[3]をソート
15 37 91 24 86 55
a[1], …, a[4]をソート
15 24 37 91 86 55
a[1], …, a[5]をソート
15 24 37 86 91 55
a[1], …, a[6]をソート
15 24 37 55 86 91
ソート終了！
挿入ソート ― その２
ここに挿入
各反復の実行方法
a[5]までソートされていると仮定
a[6]までソート
15 24 37 86 91 55
a[1], …, a[5]の間に a[6]を挿入すればよい
挿入のやり方
tmp=55
15 24 37 86 91
15 24 37
91 > 55
15 24 37 86
86 > 55
91
86 91
37≦55
15 24 37 55 86 91
挿入ソート ― その３
37 91 15 24 86 55
a[1], a[2]をソート
37 91 15 24 86 55
a[1], a[2]に a[3]を挿入
15 37 91 24 86 55
a[1], …, a[3]に a[4]を挿入
15 24 37 91 86 55
a[1], …, a[4]に a[5]を挿入
15 24 37 86 91 55
a[1], …, a[5]に a[6]を挿入
15 24 37 55 86 91
ソート終了！

選択ソート(selection sort)