Когда использовать каждый алгоритм сортировки | Набор 2

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

Зачем нужна сортировка?

Сортировка очень важна, когда необходимо сильно оптимизировать алгоритм поиска. Например, предположим два случая поиска определенного элемента.
Случай 1: Поиск элемента из случайного набора элементов. (Несортированный)
Случай 2: Поиск элемента из упорядоченного набора элементов. (Отсортировано)
Очевидно, что искать элемент в случае 2 было бы проще и быстрее, так как элементы предварительно отсортированы, поэтому поиск занял бы меньше времени.

Когда использовать каждый алгоритм сортировки?

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

• Размер данных: общее количество присутствующих элементов или данных может быть большим или маленьким.
• Состояние данных: являются ли данные полностью случайными, частично отсортированными или почти отсортированными.
• Сложность времени и пространства : количество времени и пространства, в которые нам нужно инвестировать.

Давайте посмотрим на различные алгоритмы сортировки:

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

• Лучшее в этом алгоритме то, что он не требует дополнительной памяти, поэтому, если есть потребность в алгоритме без дополнительного пространства, можно использовать сортировку кучей.
• Он демонстрирует стабильную производительность. Таким образом, он хорошо работает в лучшем, среднем и худшем случаях. Благодаря гарантированной производительности он используется в системах с критическим временем отклика.
• Куча спорта особенно подходит для сортировки огромного списка элементов.

Сложность времени:

• Лучший случай: O(N*log N)
• Средний случай: O (N * log N)
• Худший случай: O(N*log N)

Космическая сложность: O(1)

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

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

Сложность времени:

• Лучший случай: O(N*log N)
• Средний случай: зависит от последовательности пробелов
• Худший случай: O(N*log ² N)

Космическая сложность: O(1)

Radix Sort : это несравнительный алгоритм сортировки. Это позволяет избежать сравнения, создавая и распределяя элементы по корзинам в соответствии с основанием. Он имеет линейную временную сложность, которая лучше, чем O (N * log N) алгоритмов сравнительной сортировки. Сортировка по основанию может использоваться в соответствии с приведенными ниже ограничениями:

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

Сложность времени:

• Лучший случай: O(N*K)
• Средний случай: O(N*K)
• Худший случай: O(N*K)

Космическая сложность: O(N + K)

Bucket Sort : Bucket sort работает путем распределения элементов массива по нескольким сегментам. Затем каждое ведро сортируется индивидуально и добавляется в один массив. Это довольно стабильный алгоритм, так как после того, как элементы распределены по корзинам, каждая корзина может обрабатываться независимо от других. Сортировка ведра может использоваться в соответствии с приведенными ниже ограничениями:

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

Сложность времени:

Лучший случай: O(N + K)
Средний случай: O(N)
Худший случай: O(N ² )

Космическая сложность: O(N*K)

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

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

Сложность времени:

• Лучший случай: O(N + K)
• Средний случай: O(N + K)
• Худший случай: O(N + K)

Космическая сложность: O(N + K)