Bubble sort · Пузырьковая сортировка
Sorting puts items in order
- Sorting rearranges a list into order — smallest to largest, say.
- Bubble sort is the standard method named in the syllabus.
- It compares neighbours and swaps any that are the wrong way round.
Сортировка упорядочивает элементы
- Сортировка упорядочивает список — от наименьшего к наибольшему, например.
- Пузырьковая сортировка — стандартный метод, указанный в программе.
- Она сравнивает соседние элементы и меняет местами те, что расположены неверно.
Swapping two values
- To sort, you must swap two items.
- Python can swap in one line:
a, b = b, a.
Обмен двумя значениями
- Для сортировки необходимо поменять местами два элемента.
- В Python можно поменять значения местами в одну строку:
a, b = b, a.
a = 5
b = 9
a, b = b, a
print(a, b) # 9 5
Bubble sort: compare neighbours
- Walk the list comparing each pair of neighbours.
- If the left one is bigger, swap them — the biggest "bubbles" to the end.
- Repeat the passes until the list is in order.
Пузырьковая сортировка: сравнение соседей
- Пройдите по списку, сравнивая каждую пару соседних элементов.
- Если левый элемент больше, поменяйте их местами — самый большой «всплывает» в конец.
- Повторяйте проходы, пока список не будет отсортирован.
nums = [5, 1, 4, 2]
for i in range(len(nums) - 1):
for j in range(len(nums) - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums) # [1, 2, 4, 5]
In the exam: bubble sort
- The exam writes bubble sort in pseudocode with nested loops and a swap.
На экзамене: пузырьковая сортировка
- На экзамене пузырьковая сортировка записывается псевдокодом с вложенными циклами и обменом.
FOR I ← 1 TO N - 1
FOR J ← 1 TO N - 1
IF List[J] > List[J + 1]
THEN
Temp ← List[J]
List[J] ← List[J + 1]
List[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
Watch bubble sort work · Посмотрите, как работает сортировка пузырьком
Compare neighbours and swap any out of order; the biggest bubbles to the end. · Сравнивайте соседние элементы и меняйте местами те, что стоят не по порядку; самые большие «пузыри» всплывают в конец.
Common mistakes
- Each pass moves the largest remaining value to the end.
- If a whole pass makes no swaps, the list is already sorted.
Распространенные ошибки
- Каждый проход перемещает наибольшее оставшееся значение в конец.
- Если весь проход проходит без обменов, список уже отсортирован.
Now you try
- Swap two values, then sort a whole list.
- Press Check answer to test your code.
Теперь попробуйте сами
- Поменяйте местами два значения, затем отсортируйте весь список.
- Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Swap the values of a and b, so that afterwards a is 9 and b is 5. · Поменяйте значения a и b местами, так что после этого a станет 9, а b станет 5.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Sort the list nums into ascending order (smallest first) using a bubble sort. The result should be [1, 2, 4, 5]. · Отсортируйте список nums по возрастанию (от меньшего к большему) методом сортировки пузырьком. Результат должен быть [1, 2, 4, 5].
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write is_sorted(nums) that returns True if the list is already in ascending order, otherwise False. · Напишите is_sorted(nums), которая возвращает True, если список уже отсортирован по возрастанию, иначе возвращает False.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.