Repository files navigation

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²).