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

Понятие внутренней и внешней сортировки

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

Сортировка – это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ³, £, =. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг с другом в любом порядке. Хотя иногда, бывает полезно сохранить первоначальный порядок элементов с одинаковыми значениями.

Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации. Некоторые задачи обработки данных решаются проще, если данные упорядочены.

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

На практике редко требуется упорядочивать числа как таковые. Обычно надо сортировать записи (records), содержащие несколько полей, и располагать их в порядке, определяемом одним из полей. Например, в архиве отдела кадров для каждого сотрудника фирмы может храниться запись, содержащая различные поля (фамилия, имя, отчество, год рождения, адрес и т.п.), и в какой-то момент может понадобиться упорядочить все записи по годам рождения. Поле, по которому проводится сортировка (год рождения в нашем примере), называется ключом (key), а остальные поля – дополнительными данными (satellite data).

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

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

В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.

Пусть отсортировано начало массива A [1], A [2],..., A [ i – 1], а остаток массива A [ i ],..., A [ n ] содержит неотсортированную часть. На очередном шаге будем включать элемент A [ i ] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A [ i ], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A [ i ]. Но при сдвиге будет потеряно само значение A [ i ], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A [ i ] в промежуточной переменной. Так как массив из одного элемента можно считать отсортированным, то необходимо начать с i = 2.