Сортировка методом пузырька

Описание алгоритма

  1. Проход по неупорядоченному множеству (например, списку). При этом, если последующий элемент меньше предыдущего, то они меняются местами. В итоге, самый «тяжелый» элемент оказывается в конце множества. Пример: дано: 4, 7, 3, 6, 1 меняем: 7 и 3, затем 7 и 6, затем 7 и 1 результат: 4, 3, 6, 1, 7
  2. Проход по множеству, исключая последний элемент, т.к. он уже отсортирован. При проходе обмен меньшего последующего на больший предыдущий.
  3. Количество проходов по множеству равно количеству элементов минус 1. Последний проход не нужен, т.к. остается один элемент, и его значение меньше остальных. Он «всплыл» в результате предыдущих проходов.

Исходный код на Python

li = [5,2,7,4,0,9,8,6] 
n = 1 
while n < len(li):
     for i in range(len(li)-n):
          if li[i] > li[i+1]:
               li[i],li[i+1] = li[i+1],li[i]
     n += 1

Переменная n здесь служит для того, чтобы прервать проходы по списку, как только ее значение приблизится к размеру длины строки. Также цикл for благодаря n сокращается при каждом последующем проходе по while. Это оптимизирует алгоритм: последние элементы не просматриваются. Элементы меняются местами лишь в случае, если предыдущий элемент больше последующего.

Создано