Мотивация

Цель этого поста — сравнить наиболее заметные алгоритмы сортировки массивов, рассмотреть варианты их использования и кратко изложить теорию, лежащую в основе каждого из них. У каждого алгоритма есть свои особенности, плюсы и минусы. Я проведу сравнение между ними, чтобы вы попытались определить, в каких ситуациях каждый алгоритм будет более подходящим для ваших вариантов использования.

Алгоритмы

Пузырьковая сортировка (или сортировка погружением) — это прямой алгоритм стабильной сортировки сравнением, который непрерывно сравнивает соседние индексы и меняет их местами, если они не в порядке. Временная сложность алгоритма 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 элемента, он сначала анализируется, а затем разбивается на прогоны, которые складываются, а затем объединяются в соответствии с критериями.

Если вы хотите узнать больше, прочитайте эти статьи об алгоритме:

Сложность:

Время: 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.