Содержание
Упорядочивание набора элементов в списке - частая задача в программировании. Часто человек может выполнить эту задачу интуитивно. Однако компьютерная программа должна следовать точной последовательности инструкций для ее выполнения, и эта последовательность называется алгоритмом. Алгоритм упорядочивания - это метод, используемый для размещения списка неорганизованных элементов в заданном порядке. Последовательность заказа определяется ключом. Есть несколько алгоритмов сортировки, которые различаются по эффективности и производительности. Вот некоторые известные и важные из них: пузырьковая сортировка, сортировка по выбору, сортировка вставкой и быстрая сортировка.
Пузырьковая сортировка
Пузырьковая сортировка неоднократно меняет соседние элементы, которые не находятся в порядке, пока не будет построен весь список элементов. Таким образом, элементы плавают в списке в соответствии со своими значениями, причем наибольший (в случае сортировки по возрастанию) идет в конец в конце каждой итерации.
Главное преимущество этого алгоритма в том, что его реализация проста и известна. Кроме того, при пузырьковой сортировке элементы меняются местами без использования временного хранилища, что минимизирует потребность в пространстве. Основным недостатком является то, что он не дает хороших результатов, когда список содержит много элементов. Это связано с тем, что для этого типа сортировки требуется n² шагов обработки для каждого n числа элементов, которые будут отсортированы. Таким образом, пузырьковая сортировка подходит для академического образования, но не для реальных приложений.
Выборочная сортировка
Сортировка по выбору многократно выполняет поиск в списке элементов, выбирая по одному элементу за раз и помещая его в правильную позицию в последовательности.
Основное преимущество сортировки по выбору в том, что она хорошо работает с коротким списком. Кроме того, поскольку это алгоритм упорядочивания мест, он не требует временного хранения сверх того, что необходимо для хранения исходного списка. Главный недостаток - низкая эффективность на больших списках. Как и пузырьковая сортировка, для каждого n элементов требуется n² шагов. Кроме того, на его производительность легко влияет первоначальный порядок элементов перед процессом сортировки. По этой причине этот тип выбора подходит только для списка, в котором несколько элементов расположены в случайном порядке.
Вставка сортировки
Сортировка вставкой многократно просматривает список и каждый раз вставляет элемент из неупорядоченной последовательности в правильную позицию.
Основным преимуществом сортировки вставкой является ее простота, а также хорошая производительность в небольших списках. Это алгоритм размещения, поэтому занимаемая площадь минимальна. Недостатком является то, что он не работает так же хорошо, как другие алгоритмы сортировки. Поскольку для работы требуется n² шагов, сортировка вставкой также не работает с большими списками. Однако это особенно полезно для списков из нескольких элементов.
Быстрая сортировка
Быстрая сортировка работает по принципу разделения и завоевания. Во-первых, он делит список элементов на два подсписка на основе сводного элемента. Все элементы в первом подсписке расположены так, что они меньше, чем сводная таблица, в то время как все элементы во втором подсписке расположены больше, чем сводная таблица. Один и тот же процесс разделения и организации выполняется многократно для результирующих подсписок, пока не будет организован весь список.
Некоторые считают быструю сортировку лучшим алгоритмом сортировки из-за ее значительного преимущества в эффективности, так как она хорошо работает с большим списком элементов. При заказе на месте также не требуется дополнительное место для хранения. Небольшой недостаток, который он представляет, заключается в том, что его худшая производительность аналогична средней производительности других алгоритмов, описанных выше. Однако важно отметить, что этот наихудший случай встречается очень редко. В более общем смысле, быстрая сортировка является наиболее эффективным и широко используемым методом организации списка любого размера.
