このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
配列を並べ替える
- ソートとは、配列の値を並べ替えること、通常は小さい順から大きい順である。
- AP CSA試験では、2種類のソート——選択ソートと挿入ソート——を記述してトレースできる必要がある。
- また、3番目のソート——マージソート——をトレースする必要がある(記述は不要)。ここでは3つすべてを取り上げる。
選択ソート:考え方
- 左から右へ配列を進む。
- 各位置
iにおいて、まだ未整列の部分(iから末尾まで)で最小の値を見つける。 - その最小の値を位置
iと交換する。これで0..iが整列される。 - 配列全体が整列されるまで繰り返す。
English
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
選択ソート:トレース
{5, 2, 4, 1, 3}をソートする。|の左側の部分は既にソート済みである。- 各パスで残りから最小の値を選び、先頭に交换する。
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
挿入ソート:考え方
- 手札を持って、1枚ずつ正しい位置に挿入するイメージを持つ。
- インデックス
1から始める。この値をキーと呼ぶ。 - 左側の大きい値を1つ右へずらし、キーが入る位置を探す。
- ギャップにキーを落とす。これで左側はすべて整列された状態になる。
English
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
挿入ソート:トレース
{5, 2, 4, 1, 3}を再びソートする。|の左側の部分は進行に伴いソート状態を維持する。keyは各パスで挿入している値である。
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
マージソート:トレースのみ
- マージソートは再帰を使用する(Implemented in Lesson 15)。試験では記述しないが、トレースする必要がある。
- 配列を半分に分割し続け、各ピースが1つの値になるまで続ける。
- ピースのペアをマージして組み合わせ、常に整列状態を保つ。
マージソート:トレース
- 1つの値はすでに「整列済み」である。2つの整列済みのピースをマージすると、より大きな整列済みピースになる。
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- 選択ソートと挿入ソートは、大きな配列に対して遅い(約n²ステップ)。
- マージソートは、大きな配列に対して速い(約n・log n ステップ)。そのため重要である。
よくあるミス
- 選択ソートと挿入ソートはどちらもO(n²)。
- 手動で小さな配列をトレースして、ソートが正しく行われているか確認する。
あなたも試してみよう
- 各タスクには、TODOを含むメソッドの骨格が与えられる。配列をインプレイスでソートする(
a自身を変更する)。 - 隠れたHarnessが複数の配列をソートして結果をチェックする。
- Check answerを使用して提供されたテストでコードをコンパイルし、結果を確認してください。スタートファイルに表示されているクラスとメソッドのインターフェースを維持してください。
探索
選択ソート / 挿入ソート
ソートは比較とスワップを繰り返し、リストを順序立てるまで続けます。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
selectionSort(int[] a) を完成させ、選択ソートを使って配列を原地に小さい順にソートしなさい。チェッカーは複数の配列でテストします。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
insertionSort(int[] a) を完成させ、挿入ソートを使って配列を原地に小さい順にソートしなさい。チェッカーは複数の配列でテストします。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
isSorted(int[] a) を完成させて、配列が小さい順から大きい順に並んでいる場合(各要素が次の要素より <= 大きい)に true を返し、そうでない場合は false を返してください。空の配列や要素が1つの配列はソート済みとみなします。
実行ボタンをクリックして出力を確認してください。