בירור בועות
Put the smallest time first
- Four heights sit in an array. The smallest should come first.
- Compare each pair of neighbours. When the left one is larger, swap them.
- That single comparison does not finish the list. The next pair is compared after it.
DECLARE Heights : ARRAY[1:4] OF INTEGER
DECLARE J, Temp : INTEGER
Heights[1] ← 160
Heights[2] ← 152
Heights[3] ← 171
Heights[4] ← 148
FOR J ← 1 TO 3
IF Heights[J] > Heights[J + 1]
THEN
Temp ← Heights[J]
Heights[J] ← Heights[J + 1]
Heights[J + 1] ← Temp
ENDIF
NEXT J
OUTPUT Heights[1], " ", Heights[2], " ", Heights[3], " ", Heights[4]
J |
Compare | Swap? | Array after |
|---|---|---|---|
| 1 | 160 > 152 | yes | 152 160 171 148 |
| 2 | 160 > 171 | no | 152 160 171 148 |
| 3 | 171 > 148 | yes | 152 160 148 171 |
After one pass the largest value, 171, has reached the end, but the list is not sorted yet.
Repeat the pass
- One pass of the inner loop bubbles the largest value it sees toward the end.
- The outer loop repeats the pass. For
nvalues,n - 1passes are enough. - This is the syllabus's bubble sort. A linear search, which you wrote earlier, only looks. A sort rearranges.
DECLARE Names : ARRAY[1:5] OF STRING
DECLARE I, J : INTEGER
DECLARE Temp : STRING
Names[1] ← "Mei"
Names[2] ← "Ada"
Names[3] ← "Tom"
Names[4] ← "Bo"
Names[5] ← "Kim"
FOR I ← 1 TO 4
FOR J ← 1 TO 4
IF Names[J] > Names[J + 1]
THEN
Temp ← Names[J]
Names[J] ← Names[J + 1]
Names[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
FOR I ← 1 TO 5
OUTPUT Names[I]
NEXT I
- Five values need four passes, and each pass compares four pairs.
>also compares strings in alphabetical order, so the same algorithm sorts names.Tempmust have the same type as the array: hereSTRING.
Watch out
- Swap with a
Tempvariable.Score[J] ← Score[J + 1]alone deletes the left value. - The inner
NEXTnamesJ. The outerNEXTnamesI.
Stop when nothing swaps
- The fixed version always makes every pass, even when the list is already in order.
- A
BOOLEANflag,Swap, remembers whether a pass swapped anything. A pass with no swap means the list is sorted, so the loop stops. - After each pass the largest value left is in place, so
Lastshrinks by one.
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
Here the first pass swaps 2 and 1, and the second pass swaps nothing, so the sort stops after two passes instead of four.
Common mistakes
- The test is "left is greater", so the smaller value moves left. The other way sorts into reverse order.
- Arrays in this course count from 1. The last pair is the cell just before the end, and the last cell.
FOR J ← 1 TO 4on a 4-cell array readsScore[5], which does not exist. The inner loop stops one before the end.- Setting
Swap ← FALSEonce, before theREPEAT. It must be reset at the start of every pass.
Now you try
- The first task is one pass over three values. The second is the full sort of four values: work out how many passes and pairs it needs. The third reads five values and sorts them into descending order with a
Swapflag. Output each value on its own line. - Press Check answer to test it.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
The array Score מחזיק 14, 9, 11. Make אחד pass that swaps a neighbour when the left value is larger. Output the three values, one per line (9, then 11, then 14).
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
The array Score מחזיק 4, 1, 3, 2. Bubble-sort it into ascending order and output the four values, one per line.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
Read five integers into Score : ARRAY[1:5] OF INTEGER. Bubble-sort them into ירידה order, using a BOOLEAN flag Swap to stop when a pass makes no swap. Output the five values, one per line.
לחץ על הרץ כדי לראות את התוצא כאן.