Алгоритмы сортировки

Алгоритм сортировки – это алгоритм упорядочивания элементов списка. Упорядочивание производится в соответствии со значением ключа сортировки по возрастанию или убыванию его значения.

Задача алгоритмов сортировки

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

Исходный произвольный порядок:

4, 5, 3, 1, 9, 0, 7, 2, 6, 8

Отсортировано по возрастанию:

0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9

Отсортировано по убыванию:

9 > 8 > 7 > 6 > 5 > 4 > 3 > 2 > 1 > 0

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

Характеристики алгоритмов сортировки

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

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

Устойчивость – характеристика, определяющая производится ли замена элементов с одинаковым значением ключа сортировки.

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

Виды алгоритмов сортировки

Алгоритм сортировки методом пузырька – простейшая и самая медленная сортировка последовательности, в которой производится последовательная замена соседних парных элементов. В сортировке по возрастанию, элементы с большим значением смещаются к концу массива, а с меньшим к началу.

Алгоритм сортировки выбором – так же, один из самых простых алгоритмов. В нем, при сортировке по возрастанию, последовательно производится поиск наименьшего значения, которое перемещается на первую позицию. Затем в поиск в оставшейся части для второй позиции, и т.д. до завершения массива.

Алгоритм быстрой сортировки – один из самых быстрых, применяемых на практике алгоритмов внутренней сортировки.

Алгоритм сортировки перемешиванием – альтернативные названия – шейкерная сортировка или двунаправленная пузырьковая сортировка. Одна из вариаций пузырьковой сортировки.