並べ替えの途中を追う

1選択ソートは未整列部分の最小値の位置を探す

整列（ソート）は、値を昇順や降順へ並べ替える処理です。昇順の選択ソートでは、まだ整列していない部分から最小値を探し、その部分の先頭の値と交換します。1回終わるたびに、左端から一つずつ値の位置が確定します。

位置を表す変数で読むと、jは今回確定させる位置、kは比較中の位置、minIndexはそこまでで見つけた最小値の位置です。minIndexへ最小値そのものを入れるのではありません。配列の添字を1から数えるとき、[7,4,6,2,5]では、最初はj＝1、minIndex＝1です。

k＝2の値4は値7より小さいのでminIndexを2へ、k＝4の値2は値4より小さいので4へ更新します。

末尾まで比較した後、j＝1とminIndex＝4の要素を交換すると[2,4,6,7,5]になります。次は位置2以降だけを調べます。位置2の値4が既に最小なので、配列が変わらないまま2回目が終わります。まだ7と5が逆順です。

「今回交換して見た目が変わらなかった」と「全体が整列済み」は分けて判断します。

2バブルソートは隣同士を交換する

バブルソートは隣接する値を比較し、昇順に反していたら交換する処理を繰り返します。[3,1,4,2]なら最初の一巡で[1,3,4,2]→[1,3,2,4]となり、大きい4が右端に移ります。

一巡しただけでは中央の3と2が逆なので未完了です。次の比較・交換で[1,2,3,4]となります。「途中まで」と「全反復終了後」、比較の向きと交換条件を分けて読みます。

3整列済みの二つの列を併合する

併合（マージ）は、二つの整列済みの列を、一つの整列済みの列へまとめる処理です。昇順なら両方の先頭を比べ、小さい方を結果へ移します。移した列だけを一つ先へ進め、同じ比較を繰り返します。

[1,4]と[2,3]なら、まず1と2を比べて1を取り出します。次は4と2を比べて2、続いて4と3を比べて3を取り出します。一方の列が空になったら、他方に残る4を付け加えて[1,2,3,4]です。単に二つの列をつないだ[1,4,2,3]では昇順になりません。

4見た目が整っても指定された手順は続く

終了条件が「未処理の要素がなくなるまで」なら、最後の1要素も処理したと数えます。4個の配列で毎回一つ最大値を対象から除くなら対象数4→3→2→1→0で4回です。

実装によっては残り1個で止めても整列できますが、問題が指定する反復の回数はその条件で数えます。2回で止める、整った3回で止める、空になった後に5回目を数えるという読み違いを防ぎます。

5クイックソートの分割をたどる

クイックソートでは基準値を選び、その値より小さい側と大きい側に分けた後、各側にも同じ考え方を適用します。例えば[4,2,5,1,3]で3を基準にすると、小さい側は[2,1]、大きい側は[4,5]に分けられます。

小さい側を[1,2]、大きい側を[4,5]に整列すれば、全体は[1,2,3,4,5]になります。

この並びは分割の考え方を示す一例です。途中の要素交換の順番や基準値の選び方は実装で異なります。同じ値が複数ある場合も、その値をどちらへ置くか、又は等しい値をまとめるかなどの規則が必要です。指定された手順を読む問題では、最終結果が昇順になるという知識だけで途中の配列を決めないようにします。