Module (71%)
Section (25%)

Пузырьковая сортировка

Теперь, когда вы можете эффективно манипулировать элементами списков, пора научиться сортировать их. К настоящему времени изобретено множество алгоритмов сортировки, которые сильно различаются как по скорости, так и по сложности. Мы собираемся показать вам очень простой алгоритм, легкий для понимания, но, к сожалению, не слишком эффективный. Он используется очень редко, и уж точно не для больших и обширных списков.

Допустим, список можно отсортировать двумя способами:

  • возрастающий (точнее - неубывающий) - если в каждой паре соседних элементов первый элемент не больше второго;
  • убывающий (точнее - невозрастающий) - если в каждой паре соседних элементов первый элемент не меньше второго.

В следующих разделах мы отсортируем список в порядке возрастания, чтобы числа были упорядочены от наименьшего к наибольшему.

Вот список:

8
10
6
2
4

Мы попробуем использовать следующий подход: возьмем первый и второй элементы и сравним их; если мы определим, что они расположены в неправильном порядке (т.е. первое больше второго), мы поменяем их местами; если их порядок правильный, мы ничего не будем делать. Проверка нашего списка подтверждает последнее - элементы 01 и 02 расположены в правильном порядке, так как 8 < 10.

Теперь посмотрим на второй и третий элементы. Они расположены в неправильном порядке. Мы должны их поменять местами:

8
6
10
2
4

Идем дальше и смотрим на третий и четвертый элементы. Опять же, это не то, что должно быть. Мы должны их поменять местами:

8
6
2
10
4

Теперь проверяем четвертый и пятый элементы. Да, они тоже в неправильном положении. Происходит еще один обмен:

8
6
2
4
10

Первый проход по списку уже завершен. Мы все еще далеки от завершения нашей работы, но за это время произошло кое-что любопытное. Самый большой элемент, 10, уже ушел в конец списка. Обратите внимание, что это желаемое место для него. Все остальные элементы образуют живописный беспорядок, но этот уже на месте.



А теперь попробуйте представить список немного иначе, а именно так:

10
4
2
6
8

Посмотрите - число 10 находится вверху. Можно сказать, что оно всплыло на поверхность, как пузырь в бокале шампанского. Метод сортировки получил свое название от того же наблюдения - он называется пузырьковой сортировкой.

Теперь мы начнем второй проход по списку. Смотрим первый и второй элементы - нужна замена местами:

6
8
2
4
10

Время для второго и третьего элементов: мы тоже должны их поменять местами:

6
2
8
4
10

Теперь третий и четвертый элементы, и второй проход завершен, поскольку 8 уже на месте:

6
2
4
8
10

Мы немедленно приступаем к следующему проходу. Внимательно следите за первым и вторым элементами - требуется еще одна перестановка:

2
6
4
8
10

Теперь нужно поставить на место 6. Меняем местами второй и третий элементы:

2
4
6
8
10

Список уже отсортирован. Нам больше нечего делать. Это именно то, чего мы хотим.

Как видите, суть этого алгоритма проста: мы сравниваем соседние элементы, и, поменяв местами некоторые из них, достигаем своей цели.

Давайте закодируем в Python все действия, выполняемые за один проход по списку, а затем посмотрим, сколько проходов нам действительно нужно для его выполнения. Мы пока не объясняли этого, сделаем это чуть позже.