pum

"""
Здесь собраны все алгоритмы сортировок,
которые мы изучали с вами на уроке.

Каждый алгоритм помещен в отдельную функцию и помечен
сверху комментарией с названием этого алгоритма сортировки.
Если вам нужно в задаче воспользоваться каким-то алгоритмом
сортировки просто копируйте нужную функцию и вставляйте в свой
код.

Каждая функция принимает на вход список и сортирует его внутри
(то есть возвращаться ничего не будет. Функция будет сортировать
именно тот список, который вы передали).

Ниже будет пример с применением одного из алгоритмов сортировки.

P.S. Если у вас будут какие-то вопросы по коду, то смело пишите в комментариях!
Для этого нужно нажать на кнопку над кодом (она будет в виде иконки облачка с сообщением
и надписью ADD COMMENT)
"""


# Сортировка вставкой (с использованием особенностей питона)
# Видео с теорией: https://youtu.be/KZxP5JqtKKA
def SelectionSort(array):
    for i in range(len(array)):
        max_element = max(array[i:])
        array.remove(max_element) # вытаскиваем максимальный элемент из неотсортированной части списка
        arra.insert(i, max_element) # вставляем его в конец отсортированной части


# Сортировка вставкой (без использования особенностей питона)
def SelectionSort(array):
    for i in range(len(array)):
        max_element_index = i # индекс максимального элемента в неотсортированной части

        for j in range(i, len(array)):
            if array[j] > array[max_element_index]:
                max_element_index = j

        array[i], array[max_element_index] = array[max_element_index], array[i]


# Сортировка пузырьком
# Видео с теорией: https://youtu.be/MH7ch2_KG4c
def BubbleSort(array):
    is_sorted = False # маркер, который обозначает, что список отсортирован

    # пока не отсортирован...
    while not is_sorted:
        is_sorted = True # помечаем, что список отсортирован

        for i in range(len(array) - 1):
            # как только находим неотсортированную пару - помечаем список неотсортированным
            if array[i] > array[i + 1]:
                is_sorted = False
                array[i + 1], array[i] = array[i], array[i + 1]


# Сортировка подсчетом
# Видео с теорией: https://youtu.be/6dk_csyWif0
def CountSort(array):
    # создаем список с количеством того, сколько раз попадалась каждое число
    # в таком списке индекс - само число, а значение - сколько раз оно попадалось
    amounts = [0] * (max(array) + 1)

    # считаем все чиселки в списке
    for number in array:
        amounts[number] += 1

    # обновляем список так, чтобы он был отсортирован
    cursor = 0 # показывает, на какую позицию вставлять новое число

    for number in range(len(amounts)):
        # здесь мы используем особенность range, что при range(X)
        # код в теле цикла будет выполняться ровно X раз
        for _ in range(amounts[number]):
            array[cursor] = number # вставляем чиселку
            cursor += 1 # двигаем курсор вправо


# пример использования алгоритма сортировки пузырьком
array = [5, 1, 4, 3, 2] # неотсортированный список

print("Перед сортировкой:", array)
BubbleSort(array)
print("После сортировки:", array) # заметьте, что я вывожу тот же самый список!!