Skip to content

Vitaminvp/Sorting-Algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Sorting-Algorithms

Sorting Algorithms in JavaScript

Bubble sort

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

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

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

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

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

Bubble sort animation

wiki

Selection Sort

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

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

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

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

Selection Sort

wiki

Insertion Sort

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

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

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

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

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

Insertion Sort wiki

Merge Sort

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

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

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

Merge Sort wiki

Quick Sort

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

Quick Sort wiki

Shell Sort

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

  • Самый простой пример d = n / 2, d2 = d / 2 … dn = 1. O(n2)
  • Предложение Хиббарда: проверить на всем ni — 1 <= n. O(n3/2)
  • Числа Седжвика ...

Сложность алгоритма: O(n2) или O(n3/2).

Shell Sort Shell Sort

Counting Sort

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

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

Counting Sort

Comb Sort

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

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

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

Comb Sort