Как устроена сортировка
sorted упорядочивает список за нас, но полезно знать, как это делается. Сортировка выбором: найти наименьший элемент и поставить его первым, затем наименьший из остальных — вторым и так далее.
Обмен двух элементов в Python — одна строка: a[i], a[k] = a[k], a[i].
a = [5, 2, 9, 1, 7]
for i in range(len(a)):
k = i
for j in range(i + 1, len(a)):
if a[j] < a[k]:
k = j
a[i], a[k] = a[k], a[i]
print(a)
Сортировка пузырьком сравнивает соседей и меняет их местами, если они стоят не по порядку. За один проход наибольший элемент «всплывает» в конец, поэтому следующий проход на одно сравнение короче.
Если за проход не было ни одного обмена, список уже упорядочен, и можно остановиться раньше.
a = [4, 1, 3, 2]
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
print("проход", i + 1, a)
Если разных значений немного — например, оценки от 1 до 5, — сортируют подсчетом: считают, сколько раз встречается каждое значение, и выписывают значения по порядку столько раз.
Выбор и пузырек делают около n² сравнений: для 100000 чисел — 10 миллиардов. Подсчет проходит список один раз.
marks = [5, 3, 4, 5, 2, 3, 5]
count = [0] * 6
for m in marks:
count[m] += 1
result = []
for m in range(1, 6):
result += [m] * count[m]
print(count)
print(result)
Итог урока. Сортировка выбором ставит на место наименьший из оставшихся, пузырек меняет соседей, пока все не встанут по порядку. Оба делают около n² сравнений.
Когда разных значений мало, сортировка подсчетом проходит список один раз.
В следующем уроке — сортировка слиянием: она быстрая для любых данных и делает около n · log n шагов.
Урок пройден
Как устроена сортировка
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Как устроена сортировка
Сортировки в Python своими руками: выбором, пузырьком с ранней остановкой и подсчетом, обмен a[i], a[k] = a[k], a[i]. В 6 заданиях вы отсортируете числа выбором, посчитаете обмены и проходы пузырька, отсортируете оценки и буквы подсчетом и прочитаете программу: что она выведет?