11.12 演習¶

11.12.1 確認問題¶

配列 [4, 2, 5, 1, 3] が与えられます。次の操作では、いずれも小さい順にソートします。

解答

最初の 2 回は次のとおりです。

回配列の状態説明

1 [1, 2, 5, 4, 3] 最小要素 1 を先頭の要素と交換する

2 [1, 2, 5, 4, 3] 値 2 はすでにインデックス 1 にあるため、交換は不要

この時点で、先頭の 2 つの位置が確定しています。以後は [5, 4, 3] から最小要素を選び続ければよいです。
隣り合う要素を順に比較します。4 と 2 は交換し、4 と 5 は交換せず、5 と 1、5 と 3 はそれぞれ交換します。その結果は [2, 4, 1, 3, 5] で、交換回数は 3 回です。最大要素 5 が配列の末尾へ移動したため、最後の位置が確定しています。

配列 \([2_a, 2_b, 1]\) で、\(2_a\) と \(2_b\) の値は等しいものの、添字によって元の順序を区別しています。

解答

選択ソートの 1 回目では最小要素 1 を選び、先頭の \(2_a\) と交換するため、 \([1, 2_b, 2_a]\) となります。\(2_a\) は \(2_b\) の後ろへ移動し、相対的な順序が変わっています。
バブルソートでは、まず \(2_a\) と \(2_b\) を比較します。両者は等しいので交換しません。次に \(2_b\) と 1 を比較して交換すると、 1 回目の終了時は \([2_a, 1, 2_b]\) となります。\(2_a\) は引き続き \(2_b\) より前にあり、相対的な順序は変わっていません。
この例では、選択ソートは等しい要素の元の順序を変えます。バブルソートは、左側の要素が右側の要素より大きい場合にだけ隣り合う要素を交換します。等しい要素同士は交換しないため、元の順序を保てます。

学校で、8 桁に固定された多数の学籍番号をソートします。次の問いに答えてください。

解答

学籍番号には 8 個の桁があるため、最下位桁から最上位桁まで、合計 8 回処理します。各回では 0～9 だけを使って分類します。
そのまま数えるには、取り得るすべての 8 桁の値に対して位置を用意する必要があります。しかし、実際に生徒が使うのはそのうちのごく一部なので、ほとんどのカウント位置は常に 0 のままです。
基数ソートを選びます。「桁数が固定され、各桁が 10 種類の値だけを取る」という特徴を利用し、安定した分類を 8 回繰り返すだけで済むためです。 8 桁の学籍番号全体を整数のインデックスとして計数ソートを行うと、実際には現れない多数の値にもカウント位置を用意する必要があります。

整数配列 nums が与えられます。マージソートを自分で実装し、要素を非減少順に並べて返してください。言語に組み込まれたソート関数を呼び出してはいけません。

解法のヒント

整数配列 nums と 0 以上の整数 \(K\) が与えられ、配列の各要素は \(0\) 以上 \(K\) 以下です。

計数ソートを実装し、要素を非減少順に nums へ書き戻して、nums を返してください。要素同士の大小比較によって順序を決めたり、言語に組み込まれたソート関数を呼び出したりしてはいけません。

解法のヒント

回	配列の状態	説明
1	`[1, 2, 5, 4, 3]`	最小要素 1 を先頭の要素と交換する
2	`[1, 2, 5, 4, 3]`	値 2 はすでにインデックス 1 にあるため、交換は不要