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

Все алгоритмы сортировки можно поделить на две группы: сортировка сравнениями и лексикографическая сортировка. Эти два вида алгоритмов отличаются тем, что при сортировке сравнениями неизвестна внутренняя структура объектов. При этом они вообще могут иметь различную структуру, необходимо только уметь сравнивать объекты друг с другом (например, числа). На самом деле только одного сравнения объектов недостаточно, оно должно обладать еще некоторыми дополнительными свойствами, например транзитивностью, т.е. если a<b и b<c, то должно быть a<c. Предположим, что мы должны сравнивать вектора фактически являющиеся парами чисел вида r=(x,y). Определим операцию сравнения двух объектов r1=(x1,y1) и r2=(x2,y2) так: r1<r2 тогда и только тогда, когда x1<x2 или y1<y2. Удовлетворяет ли такое сравнение вышеприведенному условию? Возьмем 3 вектора: a=(3,9), b=(4,7), c=(1,8). По описанному способу сравнения получаем: a<b, b<c, но a не меньше c. Таким образом, при выборе этого отношения порядка не в каждом случае можно упорядочить заданную последовательность элементов.

Лексикографическая сортировка обычно применяется при сортировке объектов с известной внутренней структурой. Например, упорядочивание текстовых строк по алфавиту. Внутренняя структура строк известна: строка состоит из символов; количество символов алфавита ограничено.

Алгоритмы сортировки сравнениями.

Рассмотрим один из простейших алгоритмов сортировки сравнениями: так называемую пузырьковую сортировку.

Проиллюстрируем работу алгоритма на примере последовательности из 5-ти чисел: 5, 3, 1, 4, 2. Работа алгоритма пузырьковой сортировки проиллюстрирована на следующем рисунке.

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

Сколько времени будет выполняться такая сортировка? За элементарную операцию примем операцию сравнения двух элементов и подсчитаем, сколько таких операций необходимо произвести, если дан список из n элементов. На каждом шаге будет просматриваться на один элемент меньше. В худшем случае (когда исходный массив отсортирован по убыванию) каждый раз будет производиться хотя бы один обмен элементов, пока не останется только один элемент, и сортировку не закончится. На первом шаге будет сделано n-1 сравнение, на втором n-2 сравнения, и т.д. до одного сравнения. Итого, имеем арифметическую прогрессию от 1 до n-1 с n-1 элементом. Сумма этой прогрессии:

При больших значениях n эта функция ведет себя как n2. В таком случае говорят, что вычислительная сложность алгоритма равна O(n2). Эта оценка вычислительной сложности алгоритма называется асимптотической. Такая оценка обычно является достаточно плохой. Возникают вопросы: можно ли написать алгоритм, который будет работать быстрее и какой самый быстрый алгоритм вообще можно написать? Ответ – можно, и это . Невозможно написать более быстрый алгоритм сортировки сравнениями. Для лексикографической сортировки наиболее быстрый алгоритм имеет  вычислительную сложность .

При сортировке для обмена элементов списка можно использовать дополнительную переменную.

КОММЕНТАРИИ