Ходят слухи, чтобы попасть в Гугл, надо прорешать тысячу алгоритмических задачек. Тысячи у нас нет, но сотня-другая найдется. Заходите в испытания — и наслаждайтесь.
http://amp.gs/jTlrQСегодня мы расскажем про стандартную алгоритмическую задачку для программистов — «Быстрая сортировка»:
http://amp.gs/jTlrc. Вам нужно будет реализовать и экспортировать по умолчанию функцию, которая принимает на вход список и сортирует его по возрастанию.
____________________________________
Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Общая идея алгоритма состоит в следующем:
1. Выбрать из списка элемент, называемый опорным. Это может быть любой из элементов списка или же число, вычисленное на основе значений элементов.
2. Сравнить все остальные элементы с опорным и переставить их в списке так, чтобы разбить список на три непрерывных отрезка, следующих друг за другом: «меньшие опорного», «равные» и «большие».
3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
На практике список обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.
____________________________
Язык для решения задачки можно использовать любой. Все свои варианты —> пишите в комментариях (а лучше всего скидывайте ссылки на решения в GitHub или на
Repl.it). При этом у нас в испытаниях эту задачку решают 77% всех пользователей — то есть 7 человек из 10:
