Пузырьковая сортировка
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 монет + небольшой бонус за первое завершение сегодня
Массив Score содержит 14, 9, 11. Сделайте один проход, который меняет местами соседей, если левое значение больше. Выведите три значения по одному на строке (9, затем 11, затем 14).
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Массив Score содержит 4, 1, 3, 2. Отсортируйте его методом пузырька по возрастанию и выведите четыре значения, каждое на отдельной строке.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Считайте пять целых чисел в Score : ARRAY[1:5] OF INTEGER. Отсортируйте их по убыванию с помощью флага BOOLEAN Swap, чтобы остановиться, когда один проход не содержит обменов. Выведите пять значений, каждое на новой строке.
Нажмите Запустить, чтобы увидеть результат здесь.