Что касается Javascript, функция Sort( ) несколько неоднозначна. Сам Javascript не заботится о том, как происходит сортировка, обычно оставляя это «решение» в руках механизма JavaScript. Это означает, что Sort( ) может работать по-разному в разных браузерах. После того, как я обнаружил это, я решил поближе взглянуть на Sort( ) и обнаружил себя глубоко в супе компьютерных наук и математики, который называется Алгоритмы сортировки. В этом посте я расскажу о трех алгоритмах сортировки: сортировка по основанию, пузырьковая сортировка и быстрая сортировка.

По основаниюСортировать

Один из самых ранних алгоритмов сортировки восходит к 1880-м годам и приписывается человеку по имени Герман Холлерит. Холлерита следует признать в качестве государственного служащего, работающего в Бюро переписи населения США, где изобретенное им оборудование и технологии помогли провести перепись 1890 года всего за 6 лет. Это может показаться не таким уж большим делом, но перепись 1880 года заняла 8 лет, и это было почти на 13 миллионов меньше граждан для подсчета. Благодаря успеху своих счетных машин Холлерит основал компанию, которая в конечном итоге стала краеугольным камнем чего-то под названием International Business Machines Corporation. Возможно, вы слышали об этом.

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

Слово radix на самом деле происходит от латинского слова «корень», и вы можете видеть, что это отражается в том, как этот алгоритм сортировки начинается снизу (или корня) каждого значения и работает вверх. Обратите внимание, что когда процессы переворачиваются, это называется сортировкой по основанию по наибольшей значимой цифре (MSD).

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

Стабильно и не стабильно

Сейчас самое время поговорить о стабильности методов сортировки. Важно понимать разницу между «стабильными» и «нестабильными» сортировками, где «стабильность» гарантирует, что элементы с одинаковыми значениями сохранят свое относительное положение друг к другу на протяжении всего выполнения сортировки. Вероятно, лучший способ визуализировать это — подумать о сортировке колоды карт. Ниже мы видим, что 5 из ❤ и 5 из ♠ сохраняют свое положение относительно друг друга (например, с ❤ слева) в стабильном порядке, но не в нестабильном порядке. При оценке методов сортировки важно учитывать, нужна ли стабильная сортировка для вашего приложения. Поразрядная сортировка, как бы там ни было, является стабильным методом сортировки.

Пузырьковая сортировка

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

Этот тип сортировки начинается с сравнения самого первого значения со вторым. Если первое больше второго, значения меняются местами. Затем алгоритм сравнивает второе и третье значения. Этот шаблон повторяется до тех пор, пока не будет достигнут конец набора данных, после чего процесс начинается снова. Учитывая ее простоту, сила пузырьковой сортировки заключается в минимальном коде/инструкциях, необходимых для ее выполнения.

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

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

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

Да, и в 1945 году он изобрел сортировку слиянием. При сортировке слиянием набор чисел сначала делится пополам, затем снова пополам, затем снова пополам и так далее, пока не останутся только пары чисел. Каждая пара упорядочена, затем упорядоченные пары «вливаются» друг в друга.

В отличие от пузырьковой сортировки, сортировка слиянием со временем становится «быстрее», поскольку наборы чисел сортируются внутри. На приведенной ниже диаграмме синяя линия представляет собой теоретическое количество шагов (например, время/усилия/операции) для выполнения пузырьковой сортировки для заданного количества элементов, а красная линия отражает количество шагов для выполнения сортировки слиянием. того же размера. Обратите внимание, что это только средние значения, поскольку степень, в которой данные изначально не отсортированы, сильно повлияет на эффективность большинства методов сортировки.

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

До сих пор мы говорили о стабильных методах сортировки, но мне было любопытно посмотреть, как выглядит нестабильный метод сортировки. Введите быструю сортировку, созданную в 1959 году Тони Хоаром. (Можно также поблагодарить его за существование null ценностей, его «миллиардную ошибку» по его собственной оценке дела).

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

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

Вывод

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