Sorting Algorithms in JavaScript

• Bubble sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Shell Sort
• Counting Sort
• Comb Sort

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

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

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

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

Сложность алгоритма: O(n²).

wiki

Сортировка выбором Selection Sort начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном массиве).

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

В общем случае, при i-ом проходе по списку (0 ≤ i ≤ n-2) алгоритм ищет наименьший элемент среди последних n-i элементов и обменивает его с A[ i ]. После выполнения n-1 проходов список оказывается отсортирован.

Сложность алгоритма: O(n²).

wiki

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

Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора.

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

В приведённой ниже реализации на JavaScript алгоритма сортировки встаками используется именно эта стратегия выбора.

Сложность алгоритма: O(n²).

wiki

Сортировка слиянием использует подход «разделяй и властвуй» для сортировки элементов в массиве.

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

Сложность алгоритма: O(n log n).

wiki

Сложность алгоритма: O(n²).

wiki

Shell Sort «сортировкой по убыванию», улучшает Insertion Sort, разбивая исходный массив на несколько меньших подмассивов, каждый из которых сортируется с использованием Insertion Sort. Способ выбора этих подмассивов - уникальность Shell Sort. Вместо того, чтобы разбивать массив на подмассивы смежных элементов, сортировка оболочки использует интервал d, иногда называемый gap, для создания подмассива, выбирая все элементы, которые являются d-ми элементами, отдельно.

• Самый простой пример d = n / 2, d₂ = d / 2 … d_n = 1. O(n²)
• Предложение Хиббарда: проверить на всем n^{i — 1} <= n. O(n^3/2)
• Числа Седжвика ...

Сложность алгоритма: O(n²) или O(n^3/2).

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

Сложность алгоритма: O(n²).

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

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

Сложность алгоритма: O(n²).