Надо их всех разобрать.

Сортировка списка - распространенная вводная проблема при изучении алгоритмов. Вы можете сортировать списки чисел, букв или даже слов, но давайте рассмотрим простую задачу сортировки списка целых чисел: myList = [55, 29, 98, 61, 7, 31, 20, 68, 93, 10].

Это кажется тривиальной задачей, но существует множество методов для сортировки этого списка - и наш выбор алгоритма сортировки начинает иметь значение, когда список становится длиннее, у нас ограничена доступная память, и мы не хотим тратить целый день на перемешивание Поффинс, пока ждем сортировки списка. ⏳

Итак, прежде чем вы воодушевитесь и воскликнете: «Сортировка выбора, я выбираю вас!» в списке из 10 миллионов целых чисел, давайте рассмотрим ваши варианты и рассмотрим некоторые из самых популярных алгоритмов сортировки на сегодняшний день!

Сортировка вставкой = Сквиртл

Сортировка вставкой эффективна при сортировке небольших списков; это хороший стартовый алгоритм, как и Сквиртл, который наука показала - ваш лучший выбор для начинающего покемона. Но с более длинными списками сортировка вставкой может выполняться медленно, очень быстро; вам лучше развиваться, прежде чем вы попадете в Элитную Четверку.

Как это работает. Маркер перемещается по списку, при этом элементы уже отсортированы слева от маркера, а несортированные элементы - справа. При достижении нового элемента он вставляется обратно в отсортированную часть списка в нужном месте, пока все элементы не будут отсортированы.

Сортировка по выбору = Бульбазавр

Эффективность травы против первых двух лидеров спортзала означает, что Bulbasaur - естественный выбор, если вы хотите легко начать. Сортировку по выбору, безусловно, легко реализовать, и именно так большинство людей интуитивно сортируют колоду карт. Этот алгоритм ищет все большие числа по мере роста лампочки Бульбазавра по мере того, как она поглощает солнечный свет. Но, честно говоря, этот алгоритм слишком медленный для практического применения. Храните его на своем компьютере в ближайшем центре покемонов, он может пригодиться в будущем ...

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

Пузырьковая сортировка = Магикарп

Возможно, это хороший способ продемонстрировать алгоритм сортировки, но пузырьковая сортировка стала чем-то вроде шутки. Это было описано как оскорбление, слишком медленное для практического использования и жалкое оправдание для покемона. Ой, подождите, я имел в виду пузырьковую сортировку или Мэджикарп?

Как это работает: пузырьковая сортировка проходит по списку, сравнивая каждую пару соседних элементов, и меняет их местами, если они находятся в неправильном порядке. Обмен продолжается до тех пор, пока список не будет отсортирован.

Сортировка слиянием = Mewtwo

Наконец, алгоритм, достаточно мощный, чтобы подходить для легендарного покемона. Мьюту разводили специально для битв после многих лет сплайсинга генов и ДНК-инженерии. По сути, это просто разрезание ДНК на более мелкие части и их обратное объединение в желаемом порядке… не так ли? Но будьте осторожны, вам понадобится мастер-мяч для его хранения - неоптимизированная сортировка слиянием требует памяти для хранения как входных, так и выходных массивов.

Как это работает. Сортировка слиянием известна как стратегия разделяй и властвуй. Алгоритм разбивает список пополам и рекурсивно вызывает сортировку слиянием для обеих половин (снова разделяя его). По определению, список из 0 или 1 элементов сортируется, образуя базовый вариант. После того как обе половины списка отсортированы с помощью рекурсивных вызовов сортировки слияния, две половины объединяются по порядку. Слияние продолжается до тех пор, пока отсортированный список не будет завершен.

Быстрая сортировка = Иви

Быстрая сортировка, вероятно, является одним из самых популярных алгоритмов сортировки на сегодняшний день. Симпатичность Иви делает его одним из самых известных покемонов, помимо Пикачу, как для тренеров, так и для не тренеров. Но есть кое-что, чего вам нужно остерегаться; Иви имеет нестабильный генетический состав, что приводит к его многочисленным возможным эволюциям. Кроме того, держите Eevee подальше от покемонов боевого типа; если вы не будете осторожны, его худшее исполнение может быть рискованным.

Как это работает. Быстрая сортировка - это еще один алгоритм «разделяй и властвуй». Он выбирает элемент для использования в качестве точки поворота, а затем разделяет список, переставляя элементы на соответствующую сторону оси. Выбираются последующие опорные точки, и список разбивается на разделы, пока список не будет отсортирован.

Heapsort = Венозавр

Я же сказал вам, что Бульбазавр пригодится! Heapsort - это улучшенная версия сортировки по выбору, которая использует кучу (тип двоичного дерева) для сортировки списка. И когда вам нужно переключить корень максимального значения на лист и отрезать его для вашего отсортированного списка, бритвенный лист Венузавра придет вам на помощь.

Как это работает: сначала Heapsort создает кучу несортированного списка. Куча - это структура данных двоичного дерева, в которой:

  1. Каждый узел больше каждого из его дочерних узлов
  2. Дерево идеально сбалансировано
  3. Все листы находятся в крайнем левом положении.

Затем алгоритм создает отсортированный массив, многократно удаляя самый большой элемент из кучи, вставляя его в массив и исправляя кучу.

Сортировка подсчетом = Зубат

Не знаю, почему везде зубаты. Но их склонность к перемещению группами хорошо работает для сортировки с подсчетом, которая наиболее эффективна, когда у вас есть относительно небольшой набор ключей с несколькими значениями каждого из них.

Как это работает. Подсчетная сортировка работает путем подсчета количества объектов, имеющих разные ключевые значения (вид хеширования). Затем он использует счет количества этого объекта, чтобы определить его место в последовательности. Чтобы упростить это, если бы ваш список был 1, 3, 1, 2, 3, 1, вы бы знали, что, поскольку у вас есть три единицы, следующий ключ (2) будет помещен в список как 3 + 1 (4).

Радикс-сортировка = Caterpie

Катерпи - еще один покемон, с которым просто невозможно не столкнуться в больших количествах. Этот покемон с ошибкой занимает 10-е место в вашем Pokedex ... отличное число, чтобы использовать его в качестве основы для вашей сортировки по основанию! Сегментированное тело может помочь вам при подсчете целых чисел для сортировки списка.

Как это работает: Radix sort сортирует список цифра за цифрой, начиная с наименее значащей цифры до самой старшей цифры. Он использует алгоритм подсчета сортировки, создавая корзины для отдельных цифр. Например, 23, 12, 21, 14 будет отсортирован по 1 цифре первой [21, 12, 23, 14], за которой следует 10 цифра [12, 14, 21, 23].

Сортировка сна = снорлакс

Zzzzzzzzzzz. Вероятно, это не то, как вы должны сортировать список. Попробуйте это на экзамене или на собеседовании, и дикий снорлакс преградит вам путь (к любому шансу на успех).

Как это работает. Сортировка в спящем режиме создает отдельный поток для каждого элемента в списке, а затем отключает каждый поток на время, пропорциональное элементу. Поток с наименьшим временем сна (т.е. наименьший элемент) просыпается первым и печатается первым. Элементы «просыпаются» по порядку!

Я дам Alakazam выяснить код для этого.

Сортировка в Twitter = Chatot

Этот покемон говорит сам за себя. Буквально. Если сомневаетесь, спросите людей.

Как это работает: кто-то написал алгоритм, который использует Twitter API для отправки запроса с вашим списком номеров с просьбой отсортировать их. Когда кто-то отвечает отсортированным списком номеров, возвращается результат.

Вы можете найти реализацию алгоритма здесь.

Богосорт = Тогепи

Не пытайтесь делать это дома. Богосорт случайным образом перемешивает список, а затем проверяет, отсортирован ли он. Подобно метроному Тогепи, может быть, вы получите что-то хорошее… может быть, вы получите что-то ужасное. Хорошо, что Тогепи приносит удачу - она ​​вам понадобится.

На самом деле нет смысла это писать. Пожалуйста, никогда не используйте это. Если вам действительно нужно знать, алгоритм выглядит примерно так:

Это некоторые из наиболее распространенных (плюс несколько абсурдных) алгоритмов, которые вы можете использовать для сортировки списка. О, но мы так и не проверили, что произошло! Любой из этих алгоритмов вернет наш отсортированный список… myList = [7, 10, 20, 29, 31, 55, 61, 68, 93, 98]. Профессор Оук гордился бы!

Когда вы выбираете, какой алгоритм сортировки использовать на практике, вам необходимо учитывать такие особенности, как стабильность, временная сложность и пространственная сложность, а также то, как они меняются с длиной списка n. Независимо от того, начинается ли список почти в основном отсортированным, отсортированным в обратном порядке или полностью неупорядоченным, может повлиять на то, будет ли алгоритм работать в лучшем или худшем случае.

Хорошее понимание всех этих различных алгоритмов сортировки может пригодиться - никогда не угадаешь, когда будешь идти по высокой траве, и может появиться дикий несортированный список! Лучше быть готовым 😉.

На прошлой неделе в The Recurse Center я потратил некоторое время на изучение структур данных и алгоритмов. Если вам интересно узнать больше, класс CS61BL Калифорнийского университета в Беркли и Решение проблем с помощью алгоритмов и структур данных в Python были отличными ресурсами. Это часть вторая! ✅👩🏼‍💻