ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[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) 今回の授業で説明 選択ソート (selection sort) バブルソート (bubble sort) 挿入ソート (insertion sort) クイックソート (quick sort) マージソート (merge sort) などなど
選択ソート(selection sort) ― その１ a[1], …,a[6] の 中から最小値 a[min]を見つける 37 61 29 12 95 55 min = a[min] = 1 37 1 37 3 29 4 12 4 12 4 12 a[1] とa[min]を交換 55 95 37 73 61 12
選択ソート ― その２ a[2], …,a[6] の 中から最小値 a[min]を見つける 12 61 29 37 95 55 29 a[2] とa[min]を交換 55 95 37 61 29 12
選択ソート ― その３ 12 29 61 37 95 55 a[3],…,a[6]の中での最小値を見つけa[3]と交換 55 95 61 37 29 12 a[4],…,a[6]の中での最小値を見つけa[4]と交換 61 95 55 37 29 12 a[5],a[6]の中での最小値を見つけa[5]と交換 95 61 55 37 29 12 ソート完了
バブルソート(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] 55 95 a[5] とa[6]を交換 12 29 61 37
バブルソート ― その２ 37 61 29 12 55 95 a[4] ≦ [5] なのでそのまま 95 55 12 29 61 37 a[3] > [4] なので交換 95 55 29 12 61 37 a[2] > [3] なので交換 95 55 29 61 12 37 a[1] > [2] なので交換 95 55 29 61 37 12 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 55 61 95 交換 a[3]=37は3番目に小さい値 12 29 37 61 55 95 a[2]=29は２番目に小さい値
バブルソート ― その４ 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番目に小さい値 12 29 37 55 61 95 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]を挿入すればよい 挿入のやり方 91 86 37 24 15 tmp=55 15 24 37 86 91 91 > 55 37≦55 15 24 37 86 91 15 24 37 55 86 91 86 > 55
挿入ソート ― その３ a[1], a[2]をソート 55 86 24 15 91 37 a[1], a[2]に a[3]を挿入 55 86 24 15 91 37 55 86 24 91 37 15 a[1], …, a[3]に a[4]を挿入 55 86 91 37 24 15 a[1], …, a[4]に a[5]を挿入 55 91 86 37 24 15 a[1], …, a[5]に a[6]を挿入 91 86 55 37 24 15 ソート終了！