Приветствую вас, друзья. Так получилось, что практически несколько дней назад я решил повспоминать алгоритмы сортировки. Дело не простое, так как при работе с такими функциями, как sorted, со временем забывается все. Не только код, но и сами принципы.
Сегодня я решил выложить реализацию алгоритмы пузырьковым методом. Сразу начну с того, что это самый медленный из распространенных методов. Самый примитивный, и, я бы сказал, тупой (в смысле подхода). Но его нужно знать. Во первых, чтобы не повторять. Во вторых - это фундамент, основы, азы...
Суть: чтобы отсортировать список, необходимо сделать несколько проходов по нему, сравнивая соседние значения и меняя их местами, если оно требуется. Метод так называется, так как начиная от нулевого элемента, все элементы по очереди как пузырьки "всплывают" до своего места.
Дальше приведу два варианта:
1. Алгоритм сортировки пузырьковым методам по возрастанию:
>>> lst = [3,2,5,1,6,2,3,41,12,4311]
>>> t = lst[:]
>>> for i in range(0, len(t)-1):
for j in range(0, len(t) - i - 1):
if t[j] > t[j+1]: # Если элемент больше следующего, то меняем местами
t[j+1], t[j] = t[j], t[j+1] # На C++ таого не сделаешь
>>> t
[4311, 41, 12, 6, 5, 3, 3, 2, 2, 1]
2. Алгоритм сортировки пузырьковым методам по убыванию (разница от предыдущего в одном символе в операции сравнения):
>>> lst = [3,2,5,1,6,2,3,41,12,4311]
>>> t = lst[:]
>>> for i in range(0, len(t)-1):
for j in range(0, len(t) - i - 1):
if t[j] < t[j+1]: t[j+1], t[j] = t[j], t[j+1] >>> t
[1, 2, 2, 3, 3, 5, 6, 12, 41, 4311]