━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題11
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (基本的な整列アルゴリズム)

整数のデータ 4, 8, 7, 0, 3 をこの順に配列に格納して，
次の各整列アルゴリズムで値を小さい順に並べ替えるときの，配列の変化を示せ．
授業で扱った(教科書の)アルゴリズムを使い，外側のループを回るごとの
配列の中身を答えること．

(1) 単純選択ソート
(2) 単純挿入ソート
(3) バブルソート

──────────────────────────────────────

●答 (基本的な整列アルゴリズム)

(1) 単純選択ソート

実行前
４, ８, ７, ０, ３
反復ごとの結果
０, ８, ７, ４, ３
０, ３, ７, ４, ８
０, ３, ４, ７, ８
０, ３, ４, ７, ８

(2) 単純挿入ソート

実行前
４, ８, ７, ０, ３
反復ごとの結果
４, ８, ７, ０, ３
４, ７, ８, ０, ３
０, ４, ７, ８, ３
０, ３, ４, ７, ８

(3) バブルソート

実行前
４, ８, ７, ０, ３
反復ごとの結果
４, ７, ０, ３, ８
４, ０, ３, ７, ８
０, ３, ４, ７, ８
０, ３, ４, ７, ８

[解説]

(1) 単純選択ソートでは，外側のループの本体が(要素数-1)回実行される．
毎回，未整列部分から最小値を選び，未整列部分の先頭要素と交換することで，
整列済み部分を1要素ずつ増やす．

この問題の例では，最小値の選択と交換が次の通りに実行される．
反復1回目： ４, ８, ７, ０, ３ から ０ を選択，４ と交換．
反復2回目： ８, ７, ４, ３ から ３ を選択，８ と交換．
反復3回目： ７, ４, ８ から ４ を選択，７ と交換．
反復4回目： ７, ８ から ７ を選択，７ と交換 (実質的には変化なし)．

(2) 単純挿入ソートでは，外側のループの本体が(要素数-1)回実行される．
毎回，未整列部分の先頭要素を，整列部分の適切な位置に挿入することで，
整列済み部分を1要素ずつ増やす．

この問題の例では，要素の挿入が次の通りに実行される．
反復1回目： ８ を整列部分 ４ の末尾に挿入．
反復2回目： ７ を整列部分 ４, ８ の2番目に挿入． 
反復3回目： ０ を整列部分 ４, ７, ８ の先頭に挿入． 
反復4回目： ３ を整列部分 ０, ４, ７, ８ の2番目に挿入． 

(3) バブルソートでは，毎回，未整列部分を左から右へ走査して，
隣り合う2値が逆順なら交換することを繰り返す．これにより，
未整列部分の最大値を整列部分の先頭に移し，整列済み部分を1要素ずつ増やす．

この問題の例では，値の交換が次の通りに実行される．
反復1回目： (８,７), (８,０), (８,３) を交換．
反復2回目： (７,０), (７,３) を交換．
反復3回目： (４,０), (４,３) を交換．
反復4回目： 交換なし．

教科書のアルゴリズムは，交換が不要になると実行を終える．
この工夫により，入力が(ほぼ)整列済みの場合に，処理を早めに打ち切れる．
ただし，途中で打ち切って良いことの確認には，未整列部分を全て走査して
交換が起こらなかったことを確かめる必要がある．
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/