Задача U. Лекция. Простейшие сортировки ≡

Входной файл:			Ограничение времени:	1 сек
Выходной файл:			Ограничение памяти:	256 Мб

Условие

Перестановкой конечного множества называется некоторое расположение его элементов в ряд, при этом порядок их следования играет роль. Пусть (r₁, r₂, ..., r_n) — перестановка множества {r₁, r₂, ..., r_n}

Пусть надо упорядочить по возрастанию n элементов r₁,...,r_n. Будем называть эти элементы записями (records). Каждая запись r_i обладает ключом k_i, который используется для упорядочивания (или, иначе, сортировки). Помимо ключа, запись может содержать любую другую сопутствующую информацию, не влияющую на порядок записей. Запись может состоять только из ключа, например, если r₁,...,r_n — числа или строки.

Задача сортировки — найти такую перестановку записей, после которой соответствующие ключи расположились бы в порядке неубывания.

На множестве ключей должно быть определено отношение порядка R (например, "меньше" или "больше"), удовлетворяющее следующим свойствам (в задачах сортировки часто используют R = <):

1. закон трихотомии: ∀ a, b справедливо одно и только одно из отношений a R b, a = b, b R a
2. транзитивности: ∀ a, b, c: a R b, b R c⇒ a R c

Пусть, например, записью представлен человек, у которого есть имя, возраст, пол и рост. Перед нами стоит задача построить множество людей в шеренгу по росту. Ключом в таком случае будет рост, а отношение порядка — больше. Тогда рост первого человека в шеренге будет больше, чем рост второго, второй выше третьего и т.д.

Сортировка называется устойчивой, если записи с одинаковыми ключами сохраняют прежний порядок относительно друг друга.

Некоторые задачи, решаемые сортировками:

• задача группирования элементов по какому-либо признаку;
• поиск одинаковых элементов в двух или нескольких массивах последовательно (используя такой же как в этой задаче подход, можно быстро объединить два отсортированных массива в один);
• поиск информации по значениям ключей.

Сортировка вставками

Элементы просматриваются по одному, и каждый новый элемент просеивается (продвигается) влево в подходящее место среди уже отсортированных элементов. В самом начале процесса сортировки множество уже упорядоченных элементов пусто. После первого шага это множество состоит из одного элемента — первого. На втором шаге к нему добавляется второй элемент, продвигаясь при этом в самое начало списка в случае, если он меньше первого. Таким образом на i-м шаге элементы 1.. i−1 упорядочены относительно друг друга.

Cортировка пузырьком

Еще один способ сортировки: сравнить ключи k₁ и k₂, и в случае, если k₂ < k₁, поменять местами записи r₂ и r₁. То же сделать для r₂ и r₃ и т.д. для r_j и r_j+1. При таком способе сортировки записи с наибольшими ключами будут продвигаться вправо. После первого прохода наибольшая запись займет позицию n, на следующих проходах соответственно n−1, n−2 и т.д.

Сортировка выбором

Для каждого i=1,n выполнить поиск минимального элемента на отрезке [i,n] и поменять местами найденную минимальную запись с r_i. В другой версии этой сортировки обмен выполняется не после того, как найден минимум, а в тот же момент, как очередной r_j оказывается меньше r_i. По сути, это более лаконичный поиск минимума, но он может потребовать большее количество обменов, чем в первом варианте.

Для каждого элемента нужно выполнить поиск минимума среди элементов справа от него. Количество операций сравнения пропорционально количеству сочетаний из n по 2 = n(n−1)2 ≈ n².

---