Алгоритмы сортировки в основном используются для сортировки массива.

Почему важны алгоритмы сортировки

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

Классификация алгоритма сортировки

Алгоритмы сортировки можно классифицировать по следующим параметрам:

  1. На основе количества перестановок или инверсий. Это количество раз, когда алгоритм меняет местами элементы для сортировки входных данных. Selection Sort требует минимального количества свопов.
  2. Основано на количестве сравнений. Это число раз, которое алгоритм сравнивает элементы для сортировки входных данных. Используя нотацию Big-O, приведенные выше примеры алгоритмов сортировки требуют не менее O(nlogn) сравнений в лучшем случае и O(n^2) сравнений в худшем случае для большинства выходных данных.
  3. На основе рекурсии или нерекурсии Некоторые алгоритмы сортировки, такие как Quick Sort, используют рекурсивные методы для сортировки входных данных. Другие алгоритмы сортировки, такие как Selection Sort или Insertion Sort, используют нерекурсивные методы. Наконец, некоторые алгоритмы сортировки, такие как Merge Sort, используют как рекурсивные, так и нерекурсивные методы для сортировки ввода.
  4. Алгоритмы сортировки на основе стабильности называются stable, если алгоритм поддерживает относительный порядок элементов с одинаковыми ключами. Другими словами, два эквивалентных элемента остаются в том же порядке в отсортированном выводе, что и во входных данных.
  5. Insertion sort, Merge Sort и Bubble Sort стабильны
  6. Heap Sort и Quick Sort нестабильны
  7. Алгоритмы сортировки, основанные на требованиях к дополнительному пространству, называются in place, если они требуют постоянного O(1) дополнительного пространства для сортировки.
  8. Insertion sort и Quick-sort являются сортировкой in place, так как мы перемещаем элементы вокруг оси и фактически не используем отдельный массив, чего НЕТ в случае сортировки слиянием, где размер ввода должен быть выделен заранее для хранения вывода во время сортировки.
  9. Merge Sort является примером сортировки out place, поскольку для ее операций требуется дополнительное пространство памяти.

1. ПУЗЫРЬКОВАЯ СОРТИРОВКА

2. СОРТИРОВКА ВЫБОРОМ

3. СОРТИРОВКА ВСТАВКОЙ

4. БЫСТРАЯ СОРТИРОВКА

5. СОРТИРОВКА СЛИЯНИЕМ

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