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

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

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