Sort своими руками js

Распространенные алгоритмы сортировки с примерами на JavaScript

Хочешь проверить свои знания по JS?

Подпишись на наш канал с тестами по JS в Telegram!

Перевод статьи «Common Sorting Algorithms in JavaScript».

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

Мы рассмотрим следующие алгоритмы:

• Сортировка пузырьком
• Сортировка выбором
• Сортировка вставками
• Сортировка слиянием
• Быстрая сортировка
• Блочная сортировка

Примечание редакции Techrocks: объяснение алгоритмов сортировки с примерами на Python смотрите здесь.

Вспомогательные методы для перемены местами и сравнения

Мы часто будем менять местами элементы в массивах, поэтому давайте начнем с написания вспомогательного метода swap :

Также мы часто будем сравнивать элементы, поэтому, как мне кажется, будет не лишним написать отдельную функцию для этого:

Хорошо, с этим мы разобрались, можно переходить к сортировкам!

Сортировка пузырьком

Временная сложность в наилучшем случае — O(N), в наихудшем — O(N^2).

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

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

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

Сортировка выбором

Временная сложность в наилучшем и наихудшем случае — O(N^2).

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

Следующая диаграмма показывает алгоритм сортировки выбором в действии:

Сортировка вставками

Временная сложность в наилучшем случае — O(N), в наихудшем — O(N^2).

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

1. Предполагаем, что первый элемент уже отсортирован.
2. Сравниваем первый элемент со вторым: должно ли второе значение остаться на месте или же оно должно быть вставлено перед первым значением?
3. Далее аналогичное сравнение делается для третьего значения: должно ли оно быть вставлено на первую, вторую или третью позицию? И так далее.

На диаграмме вы видите пример сортировки вставками в действии:

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

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

Временная сложность в наилучшем и наихудшем случае — O(N Log N).

Алгоритм сортировки слиянием это один из алгоритмов «разделяй и властвуй»). Другими словами, он делит исходный массив на более мелкие массивы, пока каждый маленький массив не будет содержать всего одну позицию, а затем сливает маленькие массивы в более крупный и отсортированный.

Здесь реализация рекурсивная. Она состоит из двух функций: одна для деления массивов на более мелкие, а другая — для осуществления сортировки.

Вот диаграмма для визуализации процесса:

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

Временная сложность в наилучшем/среднем случае — O(N Log N), в наихудшем — O(N^2).

Быстрая сортировка это один из наиболее часто используемых алгоритмов сортировки. Подобно алгоритму сортировки слиянием, этот алгоритм также использует подход «разделяй и властвуй».

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

1. Выбираем значение в массиве, которое назовем опорным. Обычно это значение в середине массива.
2. Осуществляем операцию распределения, в результате которой значения меньше опорного смещаются влево от опорного, а большие — вправо от него.
3. Повторяем первые два шага для каждого подмассива (левого и правого), пока массивы не будут полностью отсортированы.

Блочная сортировка

Временная сложность в наилучшем/среднем случае — O(N + k), в наихудшем — O(N^2).

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

Обратите внимание, что наилучшим образом алгоритм блочной сортировки работает тогда, когда элементы можно распределить по блокам поровну. Если элементы слишком разбросаны, лучше использовать побольше блоков (и наоборот).

Следующая диаграмма показывает алгоритм блочной сортировки в действии:

Заключение

Мы рассмотрели лишь некоторые из наиболее часто встречающихся алгоритмов сортировки. На самом деле таких алгоритмов гораздо больше.

Источник

JavaScript метод sort()

Определение и применение

JavaScript метод sort() позволяет отсортировать массив путём преобразования его элементов в строки и сравнения этих строк в порядке следования кодовых символов Unicode (сортирует массив по алфавиту).

Обращаю Ваше внимание, что метод sort() не создает новый объект Array , а производит сортировку переданного массива. Элементы массива, которые не содержат элементов («дыры») будут отсортированы после элементов, которые содержат значение.

Поддержка браузерами

Метод	Chrome	Firefox	Opera	Safari	IExplorer	Edge
sort()	Да	Да	Да	Да	9.0	Да

JavaScript синтаксис:

Версия JavaScript

Значения параметров

Параметр

Описание

function ( a, b )

Функция, определяющую порядок сортировки элементов массива. Если функция сравнения используется (необязательный параметр), то должна возвращать одно из следующих значений: Отрицательное значение, если первый переданный аргумент меньше второго аргумента. В этом случае первый сравниваемый элемент будет расположен по меньшему индексу, чем второй. Ноль, если аргументы эквивалентны. Сравниваемые элементы массива останутся неизменными по отношению друг к другу, но будут отсортированы по отношению ко всем другим элементам. Положительное значение, если первый аргумент больше второго аргумента. В этом случае второй сравниваемый элемент будет расположен по меньшему индексу, чем первый.

Любая функция сравнения имеет следующую логику работы:

Пример использования

В следующем примере с использованием JavaScript метода sort() мы рассмотрим как отсортировать массив по алфавиту от a до z, так и от z до a:

В следующем примере мы рассмотрим как происходит сортировка массива, который содержит пустые элементы («дыры»):

В следующем примере мы рассмотрим как произвести сортировку массива, содержащего числовые значения в порядке возростания, или убывания значений:

Обратите внимание, что числа внутри массива перед сортировкой преобразуются в строковые значения, например, » 123 » будет следовать перед » 4 » в соответствии с порядком установленным в Unicode. Для того, чтобы отсортировать числовые значения в порядке возрастания, или убывания нам необходимо использовать функцию, которая задаст критерий сортировки. Рассмотрим следущий пример:

В этом примере для сортировки числовых значений внутри массива по возрастанию и по убыванию, мы дополнительно используем аргумент метода sort(), содержащий специальную функцию для сравнения. Она принимает два параметра, которые определяют два текущих сравниваемых значения. Например, при сортировке по возрастанию, сравниваются значения 50 и 4, функция вычисляет 50 — 4, и возвращает положительное значение, в результате чего первое значение будет отсортировано после второго.

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

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

В следующем примере мы рассмотри как отсортировать массив объектов по определенному свойству как по алфавиту, так и по числовому значению:

Источник

Array.prototype.sort()

Сводка

Метод sort() на месте сортирует элементы массива и возвращает отсортированный массив. Сортировка не обязательно устойчива (англ.). Порядок сортировки по умолчанию соответствует порядку кодовых точек Unicode.

Синтаксис

Параметры

Возвращаемое значение

Отсортированный массив. Важно, что копия массива не создаётся — массив сортируется на месте.

Описание

Если функция сравнения compareFunction не предоставляется, элементы сортируются путём преобразования их в строки и сравнения строк в порядке следования кодовых точек Unicode. Например, слово «Вишня» идёт перед словом «бананы». При числовой сортировке, 9 идёт перед 80, но поскольку числа преобразуются в строки, то «80» идёт перед «9» в соответствии с порядком в Unicode.

Если функция сравнения compareFunction предоставлена, элементы массива сортируются в соответствии с её возвращаемым значением. Если сравниваются два элемента a и b , то:

• Если compareFunction(a, b) меньше 0, сортировка поставит a по меньшему индексу, чем b , то есть, a идёт первым.
• Если compareFunction(a, b) вернёт 0, сортировка оставит a и b неизменными по отношению друг к другу, но отсортирует их по отношению ко всем другим элементам. Обратите внимание: стандарт ECMAscript не гарантирует данное поведение, и ему следуют не все браузеры (например, версии Mozilla по крайней мере, до 2003 года).
• Если compareFunction(a, b) больше 0, сортировка поставит b по меньшему индексу, чем a .
• Функция compareFunction(a, b) должна всегда возвращать одинаковое значение для определённой пары элементов a и b . Если будут возвращаться непоследовательные результаты, порядок сортировки будет не определён.

Итак, функция сравнения имеет следующую форму:

Для числового сравнения, вместо строкового, функция сравнения может просто вычитать b из a . Следующая функция будет сортировать массив по возрастанию:

Метод sort можно удобно использовать с функциональными выражениями (и замыканиями):

Объекты могут быть отсортированы по значению одного из своих свойств.

Примеры

Пример: создание, отображение и сортировка массива

В следующем примере создаётся четыре массива, сначала отображается первоначальный массив, а затем они сортируются. Числовые массивы сортируются сначала без, а потом с функцией сравнения.

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

Пример: сортировка не-ASCII символов

Для сортировки строк с не-ASCII символами, то есть строк с символами акцента (e, é, è, a, ä и т.д.), строк, с языками, отличными от английского: используйте String.localeCompare . Эта функция может сравнивать эти символы, чтобы они становились в правильном порядке.

Пример: сортировка c помощью map

Функция сравнения (compareFunction) может вызываться несколько раз для каждого элемента в массиве. В зависимости от природы функции сравнения, это может привести к высоким расходам ресурсов. Чем более сложна функция сравнения и чем больше элементов требуется отсортировать, тем разумнее использовать map для сортировки. Идея состоит в том, чтобы обойти массив один раз, чтобы извлечь фактические значения, используемые для сортировки, во временный массив, отсортировать временный массив, а затем обойти временный массив для получения правильного порядка.

Источник