Сортировка методом Пузырька. Реализация алгоритма на языке Python.

Метод пузырька

Довольно часто при решении задач приходится сортировать значения в списке (массиве) по возрастанию или убыванию. Существует большое количество различных алгоритмов сортировки. Они отличается друг от друга временем выполнения (вычислительной сложностью), используемой памятью, а также сложностью в понимании и реализации.

Можете просмотреть следующее видео — изображающее принцип работы некоторых алгоритмов сортировки:

Один из самый простых алгоритмов сортировки, изучаемый в школьном курсе информатики — «Сортировка методом Пузырька». Его нельзя назвать быстрым, но он очень прост в понимании и реализации. Подходит для сортировки небольших списков (массивов).

Работу данного алгоритма представил в виде танца коллектив из Финляндии

  Как видно из видео процесс сортировки заключается в следующем:

  1. Сравнивается i-ый элемент списка с i+1 — ым. Если больший из них имеет меньший порядковый номер, то они меняются местами (для сортировки по возрастанию)
  2. Таким образом, самый большой элемент  сдвигается в конец списка
  3. Далее процесс повторяется, но не до конца списка, а до последнего отсортированного элемента

Например:

Дан список (массив): 0, 5, 8, 4, 9, 3

Расположим элементы списка в процессе убывания. Т.е. если элемент меньше своего соседа справа — меняется с ним местами.

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

После первого прохождения по списку первый нолик становится на последнее место

Метод пузырька-2

Как можно заметить количество сравнений уменьшилось на единицу, так как число 0 — минимальное заняло свое законное место при первой итерации и сравнивать с ним нет смысла.

Метод пузырька-3

Продолжаем:

Метод пузырька-4

Последний шаг:

Метод пузырька-5

В итоге получаем отсортированный список:

Метод пузырька-6

Для списка из шести элементов достаточно выполнить  пять «проходов» по списку, поочередно сравнивая соседние элементы.

Напишем программу сортировки методом Пузырька на Python 3.

#создаем список
li = [0, 5, 8, 4, 9, 3]
#вычисляем длину списка
n = len(li)
#внешний цикл отсчитывает количество "проходов" по списку
for j in range(0,n-1):
    #вложенный цикл сравнивает i-ый c i+1 -ым элементом и при необходимости меняет их местами
    #количество сравнений каждый раз уменьшается на величину j
    for i in range(0,n-j-1):
        if li[i] < li[i+1]:
            li[i],li[i + 1] = li[i + 1], li[i]
    print(j+1, "- ый проход цикла - ",end=" ")
    print(li)
print(li)

Задачи:

  1. Отсортировать список по возрастанию суммы цифр чисел
  2. Дан список целых чисел, состоящий из 30 элементов. Найти сумму пяти самых больших и пяти самых маленьких элементов списка.
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (7 голос, значение: 3,71 из 5)
Загрузка...
Вы можете оставить комментарий, или ссылку на Ваш сайт.

Оставить комментарий

Антибот *