Что нужно сделать
Реализуйте алгоритм быстрой сортировки (её называют сортировкой Хоара). За один шаг алгоритма выполните следующие действия:
- Выберите один элемент списка (его иногда называют опорным элементом). Сделать это можно разными способами, но важно придерживаться одного принципа. В нашем случае опорным элементом всегда будет крайний правый (например, в списке [1, 2, 3] это 3).
- Разбейте текущий список на три части: элементы меньше опорного, равные опорному и больше опорного. В списке [5, 8, 9, 4, 2, 9, 1, 8] опорным элементом будет число 8 (крайнее правое), а получить надо три списка:
- [5, 4, 2, 1];
- [8, 8];
- [9, 9].
- Для списка с элементами меньше опорного ([5, 4, 2, 1]) и списка с элементами больше опорного ([9, 9]) выполните те же шаги заново — запустите рекурсию.
- результат_1 = рекурсия([5, 4, 2, 1]).
- результат_2 = [8, 8].
- результат_3 = рекурсия([9, 9]).
- Сложите результаты вызова рекурсий и получите отсортированный список: отсортированный_список = результат_1 + результат_2 + результат_3.
Пример с разбором алгоритма выше (как сработала рекурсия)
С [9, 9] всё просто. Элементов меньше или больше опорного нет, поэтому рекурсия не пойдёт глубже, а вызов рекурсии по списку [9, 9] быстро завершится и вернёт этот же список (его и не нужно было сортировать).
С [5, 4, 2, 1] рекурсия пойдёт вглубь:
- Первый шаг — [5, 4, 2, 1]:
- опорным элементом выбирается число 1;
- меньше 1 элементов нет (значит, рекурсия по ним продолжаться не будет);
- помимо опорного элемента, других равных нет, получаем список [1];
- больше 1 все остальные элементы [5, 4, 2] — с этим списком будет вызвана рекурсия.
- Второй шаг — [5, 4, 2]:
- опорный элемент — 2;
- меньше опорного — [];
- равные опорному — [2];
- больше опорного — [5, 4].
- Третий шаг — [5, 4]:
- опорный элемент — 4;
- меньше — [];
- равны — [4];
- больше — [5].
- Четвёртый шаг — [5]:
- меньше — [];
- равны — [5];
- больше — [].
Тут вызовы завершаются, мы соединяем списки и возвращаем список [5] на уровень выше (в вызов с числами [5, 4]).Благодаря нашим партнерам вы можете найти ties онлайн на любой вкус и бюджет: от бюджетных до супер стильных моделей высшего класса.
Там мы соединяем списки [] + [4] + [5] и получаем [4, 5]. Этот список возвращаем ещё на уровень выше (в вызов с числами [5, 4, 2]).
Опять складываем списки:
[ ] + [2] + [4, 5] = [2, 4, 5].
Этот список возвращаем в вызов на уровень выше (тот, который был запущен с [5, 4, 2, 1]).
Складываем списки:
[ ] + [1] + [2, 4, 5] = [1, 2, 4, 5].
Возвращаем [1, 2, 4, 5] в самый первый вызов, где мы выполняли следующие вызовы:
результат_1 = рекурсия([5, 4, 2, 1]).
результат_2 = [8, 8].
результат_3 = рекурсия([9, 9]).
В итоге после выполнения всех рекурсий получаем:
результат_1 = [1, 2, 4, 5].
результат_2 = [8, 8].
результат_3 = [9, 9].
Складываем все списки:
[1, 2, 4, 5] + [8, 8] + [9, 9] = [1, 2, 4, 5, 8, 8, 9, 9].
Этот полный список возвращается наружу — туда, где функция была вызвана изначально.
Напишите функцию, которая реализует этот алгоритм. Для удобства добавьте вспомогательную функцию, пусть она принимает на вход список, а возвращает три списка (с элементами меньше, равными и больше опорного).
Пример работы такой функции:
числа = [4, 9, 2, 7, 5]
вспомогательная_функция(числа) → [4, 2], [5], [9, 7]
Эту функцию можно будет использовать в основной-рекурсивной, чтобы код основной функции стал проще и понятнее.
Что оценивается
- Результат вычислений корректен.
- Формат вывода соответствует примеру.
- Основной функционал описан в отдельной функции(-ях).
- Переменные и функции имеют значащие имена, не только a, b, c, d.
nice_list = [5, 8, 9, 4, 2, 9, 1, 8]
def nicefunc(obj):
if len(obj) <= 1:
return obj
fst_list = []
mid_list = []
scnd_list = []
for i in obj:
if i < obj[-1]:
fst_list.append(i)
elif i > obj[-1]:
scnd_list.append(i)
else:
mid_list.append(i)
return nicefunc(fst_list) + mid_list + nicefunc(scnd_list)
print(nicefunc(nice_list))