Сортировка

Сортировка используется:

1. Для вывода в удобном виде (например, по алфавиту)

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

3. Задачи группировки: после сортировки группируемые элементы располагаются подряд ; считается, что 25% машинного времени тратится на упорядочение данных, а первый машинный алгоритм сортировки был разработан или продемонстрирован в 60-м году.

Классификация алгоритмов сортировки

Д.Кнут выделяет пять классов сортировок:

1. Класс обменных сортировок: элементы обмениваются местами, если он не упорядочены

2. Класс выбора - из неупордяченной последовательности тем или иным образом выбирается элемент, и помещается (просто добавляется в выходные последовательность, которая становится упорядоченной)

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

4. Класс сортировки подсчетом - основан на том, что свое окончательное место упорядоченной последовательности с номером j элемент занимает в том и только том случае, если в этой последовательности оказалось ровно j-1 элемент, меньшей (сортировка по возрастанию), или по больших элемент, то есть для упорядочивания, а точнее нахождения места в упорядоченной последовательности для элемента достаточно подсчитать количество меньших ключей.

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

1 - пузырек, алгоритм Хоару (quicksort)

2 - простой выбор (min/max), пирамидальная сортировка

3 - простая вставка, алгоритм Шелла, бинарная

4 - сравнение и подсчет, распределяющий обмена (часть карманной сортировки)

5 - слияние: естественное двухпутевое слияние, фиксированное двухпутевое слияние

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

Пусть имеется N элементов R1, R2, …, Rn - записи, т.к. для удобства в каждом из этих элементов одно поле ключевое, а вторые поля – сопутствующие, или информационные.

R1, R2, …, Rn

Важно: с точки зрения программирования доступ к полю k R[i].k тоже самое, что k[i], но R[i] ↔ R[j]

Ключ – это поле, которое управляет процессом сортировки, причем на множестве ключей (вспомним, что ключевое поле необязательно численное ). Определим отношение порядка “>” таким образом, чтобы для любых трех значений ключей a,b,c выполнялись следующие законы:

1. Если, а > b и b>c то a>c – закон транзитивности

2. Справедливо одно и только одно из соотношений либо a<b либо a>b либо a=b закон трихотомии

Может быть доказано, что любое множество (ключей), на котором определены отношение порядка меньше либо больше используя законы 1 и 2, может быть упорядочено, так как эти законы определяют математическое понятие линейного упорядочивания, или по-другому – совершенно упорядочение.

Тогда задача сортировки заключается, чтобы найти такую перестановку записей, чтобы ключи k1, k2, ..., kn расположились в неубывающем порядке.