GrokkingAlgorithms/10 quick sort recursion.py at main · AlexTkDev/GrokkingAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Быстрая сортировка, используя рекурсию. [O(n*log n)]

# Создаем функцию "quick_sort", которая принимает один входной параметр:
# список "list_to_sort", который содержит числа.
# Эта функция возвращает этот список отсортированный по возрастанию.

def quick_sort(list_to_sort):
    # Создаем базовый случай.
    # Базовый случай в рекурсивной функции - это часть функции, в которой описывается
    # условие прекращения работы функции в целях предотвращения зацикливания.
    # Если одна из вызванных рекурсивно копий функции "quick_sort" принимает в качестве параметра список,
    # содержащий 1 или 0 элементов, то мы выходим из этой копии функции "quick_sort" и возвращаем этот список
    # предыдущей копии функции "quick_sort" в стеке вызовов, поскольку если список содержит 1 или 0 элементов,
    # то он уже отсортирован по возрастанию.
    # Если изначально вызывается функция "quick_sort", которая принимает в качестве параметра список,
    # содержащий 1 или 0 элементов, то функция "quick_sort" сразу возвращает этот список,
    # поскольку если список содержит 1 или 0 элементов, то он уже отсортирован по возрастанию.
    # Функция "len()" возвращает количество элементов в списке.
    # Ключевое слово "return" выходит из функции и возвращает какое-либо значение.
    if len(list_to_sort) < 2:
        return list_to_sort
    # Создаем рекурсивный случай.
    # Рекурсивный случай в рекурсивной функции - это часть функции, в которой функция вызывает сама себя
    # в целях выполнения какой-либо задачи.
    # Если список "list_to_sort" содержит 2 или больше элементов, то:
    else:
        # 1. Создается переменная "pivot", которая хранит опорный элемент списка "list_to_sort",
        # который равен элементу списка "list_to_sort" под индексом 0.
        pivot = list_to_sort[0]
        # 2. Формируется подсписок элементов списка "list_to_sort",
        # которые меньше или равны опорному элементу списка "list_to_sort".
        # Для этого мы перебираем все элементы списка "list_to_sort",
        # кроме первого элемента этого списка, при помощи цикла for,
        # и сохраняем в подсписке "less" только те элементы, которые меньше или равны опорному элементу.
        less = [i for i in list_to_sort[1:] if i <= pivot]
        # 3. Формируется подсписок элементов списка "list_to_sort",
        # которые больше опорного элемента списка "list_to_sort".
        # Для этого мы перебираем все элементы списка "list_to_sort",
        # кроме первого элемента этого списка, при помощи цикла for,
        # и сохраняем в подсписке "greater" только те элементы, которые больше опорного элемента.
        greater = [i for i in list_to_sort[1:] if i > pivot]
        # 4. Рекурсивно вызываются копии функции "quick_sort" для подсписков "less" и "greater",
        # при этом результаты работ этих рекурсивно вызванных копий функции "quick_sort" конкатенируются
        # с опорным элементом (["less" + "pivot" + "greater"]).
        # Когда рекурсивно вызывается копия функции "quick_sort", которая принимает в качестве параметра список,
        # содержащий 1 или 0 элементов, то срабатывает базовый случай.
        # Копии функции "quick_sort" в стеке вызовов поочередно завершают свою работу и
        # возвращают свои рассчитанные значения предыдущим рекурсивно вызванным копиям функции "quick_sort" до тех пор,
        # пока не завершит работу самая первая вызванная функция "quick_sort".
        return quick_sort(less) + [pivot] + quick_sort(greater)


# Пытаемся отсортировать список [2, 0, 6, 9, 7, 7] по возрастанию.
# Функция "print()" выводит некую указанную информацию на экран или на какое-либо другое устройство вывода.
print(quick_sort([2, 0, 6, 9, 7, 7]))