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

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

Условие

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

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

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

На множестве ключей должно быть определено отношение порядка 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ортировка пузырьком
Еще один способ сортировки: сравнить ключи k1 и k2, и в случае, если k2 < k1, поменять местами записи r2 и r1. То же сделать для r2 и r3 и т.д. для rj и rj + 1. При таком способе сортировки записи с наибольшими ключами будут продвигаться вправо. После первого прохода наибольшая запись займет позицию n, на следующих проходах соответственно n − 1, n − 2 и т.д.

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

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


0.059s 0.013s 13