Sorting · Сортировка
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
Упорядочивание элементов
- Сортировка arrangees список в порядке, обычно от наименьшего к наибольшему.
- Ключевое действие — обмен: обмен двумя элементами местами.
- В Python:
a[i], a[j] = a[j], a[i]меняет два элемента списка за одну строку.
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
Пузырьковая сортировка
- Сравнивайте каждую пару соседних элементов; меняйте их местами, если они не в порядке.
- После одного полного прохода самый большой элемент «всплывает» в конец.
- Повторяйте проходы, пока не потребуются обмены.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
Сортировка вставками
- Рассматривайте левую часть списка как уже отсортированную.
- Возьмите следующий элемент и сдвиньте его влево, пока он не займет правильное место.
- Как сортировка игральных карт в руке, по одной.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
Сравните их
- Обе проверяют примерно
n × nпар, поэтому обе медленные на больших списках. - Сортировка вставками быстра, когда список уже почти отсортирован.
- Существуют более быстрые методы, но пузырьковая и сортировка вставками легко понятны.
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
В псевдокоде Cambridge
- Пузырьковая сортировка со переменной
tempдля обмена.
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
Распространенные ошибки
- И пузырьковая, и сортировка вставками имеют сложность O(n²).
- Протraceйте маленький список вручную, чтобы проверить, работает ли ваша сортировка.
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
Теперь попробуйте сами
- Каждая задача изменяет список на месте — возвращать его не нужно.
- Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Watch a sort run · Просмотр работы сортировки
Sorting repeatedly compares and swaps until everything is in order. · Сортировка многократно сравнивает и меняет местами элементы, пока всё не будет упорядочено.
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · Напишите функцию swap(items, i, j), которая меняет местами элементы с индексами i и j в списке. Измените список на месте (без возврата значения).
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · Напишите функцию bubble_sort(items), которая сортирует список по возрастанию с использованием сортировки пузырьком. Измените список на месте.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · Напишите функцию insertion_sort(items), которая сортирует список по возрастанию с использованием сортировки вставками. Измените список на месте.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.