Мотивация
Цель этого поста — сравнить наиболее заметные алгоритмы сортировки массивов, рассмотреть варианты их использования и кратко изложить теорию, лежащую в основе каждого из них. У каждого алгоритма есть свои особенности, плюсы и минусы. Я проведу сравнение между ними, чтобы вы попытались определить, в каких ситуациях каждый алгоритм будет более подходящим для ваших вариантов использования.
Алгоритмы
Пузырьковая сортировка (или сортировка погружением) — это прямой алгоритм стабильной сортировки сравнением, который непрерывно сравнивает соседние индексы и меняет их местами, если они не в порядке. Временная сложность алгоритма O(n²), пространственная сложность O(1).
Обычно используется при подходах грубой силы. Это эффективно, когда количество элементов массива невелико, поскольку в среднем и худшем сценариях сложность будет равна 0 (n²).
Сложность:
Время: 0(n²)
- Вложенные циклы
- Для n предметов n возможных обменов
Пробел: 0(1)
- Работает на месте (для подкачки нужна только одна временная переменная)
1.1 Оптимизирована пузырьковая сортировка
Эта оптимизация немного снижает стоимость алгоритма в тех случаях, когда массив может быть относительно хорошо отсортирован на входе. Конечно, в худшем случае, когда массив отсортирован в обратном порядке, это не будет иметь никакого эффекта, на самом деле это будет даже хуже из-за дополнительной операции «если». В этом подходе вы можете определить, является ли массив уже отсортированным массивом на первом проходе с временной сложностью O (1).
2. Сортировка выбором
Сортировка выбором — это нестабильный алгоритм сортировки сравнением с низкой производительностью, полезный для небольших массивов. Он использует алгоритм сравнения на месте, в котором массив делится на 2 части: отсортированную часть и несортированную часть. Отсортированная часть начинается как пустая, но пока алгоритм следует своему пути, он будет непрерывно перемещать несортированные элементы из несортированной части в отсортированную часть. Он использует метод выбора и работает на O (n²) в лучшем, среднем и худшем случае.
Сложность:
Время: 0(n²)
- Вложенные циклы
- работает на O (n²) в лучшем, среднем и худшем случае
- Разбивает массив на несортированные и сортирует
Пробел: 0(1)
- Работает на месте (для подкачки нужна только одна временная переменная)
3. Сортировка вставками
Сортировка вставками — это простой алгоритм сортировки стабильным сравнением с низкой производительностью, полезный для небольших наборов данных или частично отсортированных данных. Он имеет низкую производительность, когда данные сортируются в порядке убывания, а вы хотите отсортировать их в порядке возрастания. Алгоритм считает первый элемент массива отсортированным, затем выбирает ближайшее значение и сравнивает их. Если следующее значение соответствует критериям сортировки (будь то сортировка по возрастанию или по убыванию), оно меняет местами значения. Затем мы переходим к следующему значению (2-й индекс в массиве), он будет сравниваться с 1-й и 0-й позициями, меняя местами значения в массиве в соответствии с критериями сравнения. Этот процесс повторяется до тех пор, пока не будет достигнут конец массива.
Сортировка вставками использует метод вставки, и хотя в лучшем случае она может выполняться за O(n), в среднем и худшем случае она работает за O(n²).
Сложность:
Время: 0(n²)
- Вложенные циклы
- в худшем случае работает за O(n²), в лучшем случае заменяется O(N) и O(1)
Пробел: 0(1)
- Работает на месте (для подкачки нужна только одна временная переменная)
4. Быстрая сортировка
Быстрая сортировка — это нестабильный алгоритм сортировки сравнением с посредственной производительностью. Рекурсивный алгоритм работает, выбирая элемент в качестве опорного элемента (в этой версии реализация выбирает последний элемент) и разбивает массив вокруг опорного элемента. Затем все элементы, меньшие, чем стержень, располагаются слева от стержня, а большие — справа. Выбор точки опоры, независимо от того, хотите ли вы, чтобы она была первой или последней среди среднего элемента, является важной частью алгоритма, потому что у них будут разные плюсы и минусы.
Быстрая сортировка использует метод разделения (или алгоритм «разделяй и властвуй», такой как сортировка слиянием) и может выполняться в лучшем случае и в среднем за O (n log (n)). Однако в худшем случае он может работать при O (n²), что делает его посредственным алгоритмом.
Сложность:
Время: 0(n²)
- Вложенные циклы
- в худшем случае работает за O(n²), в лучшем случае заменяется O(N) и O(1)
Пробел: 0(1)
- Работает на месте (для подкачки нужна только одна временная переменная)
5. Сортировка слиянием
Алгоритм сортировки слиянием представляет собой алгоритм «разделяй и властвуй». Разделите сортировку на более мелкие задачи для решения (меньшие фрагменты).
Сортировка слиянием — это стабильный алгоритм сортировки сравнением с исключительной производительностью. Сортировка слиянием использует метод слияния и выполняет O(n log (n)) в лучшем, среднем и худшем случае.
6. Собственная сортировка Node v12
Timsort — это быстрый алгоритм сортировки, эффективный для реальных данных, основанный на алгоритмах сортировки вставками и сортировки слиянием. созданный Тимом Питерсом в 2002 году для языка программирования Python. Он имеет временную сложность O (n log n) в худшем случае. Если в массиве меньше 64 элементов, сортировка выполняется как сортировка вставками. Если список превышает 64 элемента, он сначала анализируется, а затем разбивается на прогоны, которые складываются, а затем объединяются в соответствии с критериями.
Если вы хотите узнать больше, прочитайте эти статьи об алгоритме:
- https://v8.dev/blog/массив-сортировка
- https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399
Сложность:
Время: O(n log n)
- лучший случай: O(n)
- средний и худший случаи: O (n log n)
7. Результаты сравнения
Код, используемый для сравнения алгоритмов:
7.1. Сортировка небольшого количества элементов ‹ 64:
7.2. Сортировка среднего количества Элементов › 64:
7.3. Огромное количество Элементов › 100 000:
Вывод
Глядя на таблицу 7.1, мы можем заметить, что для небольшого количества элементов простые алгоритмы грубой силы могут быть очень эффективными. Алгоритмы с более чем 10 элементами, такие как быстрая сортировка и сортировка вставками, становятся более эффективными. SelectionSort идет после, но работает хуже, когда количество элементов имеет несколько повторяющихся значений.
В таблице 7,2 для списков, содержащих более 64 элементов, мы видим, что быстрая сортировка очень хорошо работает с массивами без большого количества повторяющихся элементов. Но когда мы получаем доступ к его производительности с помощью повторяющихся элементов, он не работает гораздо хуже, чем mergeSort или timSort. Сортировка вставками и сортировка выбором по-прежнему хорошо работают, когда количество элементов составляет около 200, но они быстро уступают сортировке слиянием и собственной сортировке узлов (timSort), как только количество элементов начинает немного расти.
Для списков с очень большим количеством элементов мы можем ясно видеть, что mergeSort и timSort уничтожают остальных конкурентов. Для повторяющихся элементов собственная реализация сортировки даже превзошла мою реализацию mergeSort.