Сортировки

Постановка задачи

Для элементов некоторого множества P введены соотношения сравнения. Под этим будем подразумевать следующее: для каждых двух элементов a,b Î P верно ровно одно из трех соотношений: a<b, a>b, a=b. Эти соотношения должны обладать свойствами транзитивности:

a<b, b<c Þ a<c

a>b, b>c Þ a>c

a=b, b=c Þ a=c

и аналогом свойства симметричности:

a<b Û b>a

Пусть дано некоторое упорядоченное подмножество (последовательность) элементов из P : {a₁, …, a_N}, a_iÎ P. Требуется найти такую перестановку (x₁,…,x_N), что a_x1, …, a_xN – будет неубывающей последовательностью, т.е. a_xi < a_x(i+1) или a_xi = a_x(i+1) . Напомним, что перестановкой n элементов мы называем некоторое взаимно-однозначное соответствие множества чисел {1,…,N} с таким же множеством чисел {1,…,N}, т.е. такую функцию s: {1,…,N} -> {1,…,N}, для которой если i¹j , то s(i)¹s(j).

Здесь, конечно, надо сразу задаться вопросом: а возможно ли это сделать при данных ограничениях на приведенные операции сравнения? Другим разумным вопросом будет: а если это можно сделать, то единственным ли (с точностью до перестановок подряд идущих элементов, между которыми выполняется соотношение =) способом? Ответы на оба вопросы положительны.

Доказательства утверждения, кроющегося в первом вопросе (о существовании перестановки), легко провести по индукции по n.

Для доказательства утверждения, кроющегося во втором вопросе (о единственности перестановки), можно сначала показать, что в упорядоченном множестве элементы, между которыми выполняется соотношение = должны идти подряд, что дает возможность заменить их одним элементом. Далее можно ввести функцию M(i) – количество элементов из {a₁, …, a_N}, меньших a_i. Отметим, что для любых i≠j выполняется: M(i)≠M(j) (действительно: выполняется либо a_i < a_j, либо a_i > a_j, откуда легко вывести, что, соответственно, M(i)<M(j) , либо M(i)>M(j)), из чего сразу вытекает (учитывая, что 0≤M(i)<n), что функция M(i) принимает все возможные значения от 0 до n-1. Легко показать, что эта функция однозначно определяет положение элемента a_i в упорядоченном множестве.

Отметим, что при выполнении вышеприведенных аксиом достаточно определить только одну операцию < . Тогда все остальные операции выписываются с ее помощью:

a>b Û b<a

a=b Û !(b<a && a<b)

Поэтому, при программировании алгоритма сортировки достаточно определить только одну функцию сравнения < .

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