Информатика в школе

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

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

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

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

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

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

Например:

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

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

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

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

Продолжаем:

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

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

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

Напишем программу сортировки методом Пузырька на 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 элементов. Найти сумму пяти самых больших и пяти самых маленьких элементов списка.