МІНІСТЕРСТВО  ОСВІТИ  ТА  НАУКИ УКРАЇНИ КИЇВСЬКА   ДЕРЖАВНА   АКАДЕМІЯ ВОДНОГО   ТРАНСПОРТУ імені гетьмана Петра-Конашевича Сагайдачного   КОНТРОЛЬНА РОБОТА З  ДИСЦИПЛІНИ  “ Моделювання інформаційних потоків ”

студента 5 курсу  

заочного відділення спеціальності

“Менеджмент організацій”

К И Ї В - 2 0 0 6

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

Пусть надо упорядочить N элементов R1, R2…Rn.

Назовем их записями, а всю совокупность N назовем файлом. Каждая запись Rj имеет свой ключ Kj, который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную «сопутствующую информацию», которая не влияет на сортировку, но всегда остается в этой записи.

Отношение порядка « < » на множестве ключей т.о., чтобы для всех 3-х значений ключей а, в, с выполнялись следующие условия:

1)    справедливо одно и только одно из соотношений: а< b, a=b, b<a (закон Трихотомии);

2)    если а< b и b<с, то а<с (закон Транзит-ти).

Эти 2 свойства определяют математическое понятие линейного упорядочения, которое называют еще совершенным упорядочением. Любое множество с отношением « < », удовлетворяемых свойствам 1) и 2), поддается сортировке большинством методом сортировки, который мы будем рассматривать, хотя некоторые из них годятся только для числовых и буквенных ключей с обычным отношением порядка.

Задача сортировки - найти такую перестановку записей p(1), p(2), p(n) после К ключи расположились бы в неубывающем порядке:

Kp(1)<Kp(2)<...<Kp(n)

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

Р(i)<Р(j), если Kp(i)=Kp(j) и i<j

Обычно сортировку подразделяют на 2 класса:

•     внутреннюю, если записи, которые сортируются, находятся в операционной памяти;

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

Ограничим наше рассмотрение лишь внутренними сортировками. Алгоритмы сортировки можно подразделить на несколько групп:

A. Сортировка вставками. Элементы просматриваются по одному, и каждый новый
элемент вставляется в подходящее место среди ранее упорядоченных элементов.

B. Обменная сортировка. Если два элемента расположены не по порядку, то они
меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены.

C. Сортировка посредством выбора. Сначала выделяется наименьший (или, может быть,
наибольший) элемент и каким-либо- образом отделяется от остальных, затем выбирается
наименьший (наибольший) из оставшихся и так далее.

Д. Сортировка подсчетом. Каждый элемент сравнивается со всеми остальными, окончательное положение элемента определяется подсчетом числа наименьших ключей.

Е. Специальная сортировка, которая хороша для нескольких элементов, но не поддается простому обобщению на случай большего числа элементов.

Сортировка выполняется или над самими записями, или над указателями некоторой вспомогательной таблицы, например, рассматриваем рис.1, на котором представлен файл с 5 записями. Если этот файл отсортировать в возрастающем порядке по указанному числовому ключу, то результирующий файл будет таким, как показано на рис.2. ............