バブルソート
このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
最も短い時間を先頭に置く
- 3つのレースタイムが配列
14、9、11にあります。最小値が最初に来るべきです。 - 隣り合うペアをそれぞれ比較します。左側の方が大きい場合は交換します。
- その単一の比較だけではリストが完了しません。その後、次のペアが比較されます。
English
DECLARE Score : ARRAY[1:3] OF INTEGER
DECLARE J, Temp : INTEGER
Score[1] ← 14
Score[2] ← 9
Score[3] ← 11
FOR J ← 1 TO 2
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
パスを繰り返す
- 内側のループのパスは、見た最大値を末尾へバブルさせます。
- 外側のループがパスを繰り返します。4つの値の場合、3回のパスで十分です。
- これはカリキュラムのバブルソートです。線形探索(以前書いたもの)は単に探すだけで、ソートは並べ替えます。
English
DECLARE Score : ARRAY[1:4] OF INTEGER
DECLARE I, J, Temp : INTEGER
Score[1] ← 4
Score[2] ← 1
Score[3] ← 3
Score[4] ← 2
FOR I ← 1 TO 3
FOR J ← 1 TO 3
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
OUTPUT Score[4]
注意
Temp変数を使って交換します。Score[J] ← Score[J + 1]だけでは左側の値が削除されてしまいます。- 内側の
NEXTはJという名付けをします。外側のNEXTはIという名付けをします。
スワップがないまで停止する
- 修正版は常にすべてのパスを実行しますが、リストが既に整列している場合でも除外されません。
BOOLEANフラグ、Swapは、パス中にスワップが行われたかどうかを記憶します。スワップがないパスはリストが整列していることを意味するため、ループは終了します。- パス毎に、残った最大値が正しい位置に配置されるため、
Lastは1つずつ縮小する。
DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE J, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
Score[1] ← 2
Score[2] ← 1
Score[3] ← 3
Score[4] ← 4
Score[5] ← 5
Last ← 4
REPEAT
Swap ← FALSE
FOR J ← 1 TO Last
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT J
Last ← Last - 1
UNTIL NOT Swap OR Last = 0
FOR J ← 1 TO 5
OUTPUT Score[J]
NEXT J
ここでは、最初のパスで2と1を入れ替え、2番目のパスでは入れ替わらないため、4回ではなく2回のパス後にソートが終了する。
よくあるミス
- テストは「左側が大きいか」なので、小さい値が左へ移動します。逆方向にすると降順になります。
- このコースにおける配列は1 から始まります。最後のペアは終端の直前のセルと、最終セルです。
FOR J ← 1 TO 4が4配列の要素にアクセスすると、Score[5]を読み出そうとするがそれは存在しない。内部ループは終端より1つ前で停止する。Swap ← FALSEをREPEATの前に一度だけ設定する。各パスの開始時にリセットしなければならない。
あなたも試してみよう
- 第1のタスクは1回のパスである。第2のタスクは完全なソートである。第3のタスクは5つの値を読み込み、
Swapフラグを使って降順にソートする。各値を別行で出力する。 - Check answer を押して確認する。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
配列Score には14, 9, 11 が格納されています。左の値が大きい場合に隣接する要素と入れ替える一度だけのパスを実行してください。3つの値を1行ずつ出力してください(まず9、次に11、最後に14)。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
配列Scoreには4、1、3、2が含まれています。昇順にバブルソートして、4つの値を1行ずつ出力します。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
Score : ARRAY[1:5] OF INTEGERに5つの整数を読み取ります。バブルソートで降順に並べ替え、BOOLEANフラグSwapを使用して、パス中に交換が行われなくなった段階で停止してください。5つの値を各行ごとに出力してください。
実行ボタンをクリックして出力を確認してください。