Структуры и алгоритмы обработки данных


Краткая теория - часть 2


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

Прежде чем идти дальше, введем некоторые понятия и обозначения. Ими мы будем пользоваться далее. Если у нас есть элементы а1, а2,..., аn, то сортировка есть перестановка этих элементов массив ак1, ак2, ..., акn, где при некоторой упорядочивающей функции f выполняются отношения f аk1 <= f аk2 <= ... <= f аkn. 

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

Говоря об алгоритмах сортировки, мы будем обращать внимание лишь на компоненту - ключ, другие же компоненты можно даже и не определять (рис.2). Поэтому из наших дальнейших рассмотрений вся сопутствующая информация. Чтобы уменьшить эти затраты, сортировку производят в таблице адресов ключей. После сортировки перестанавливают указатели. Это метод сортировки таблицы адресов (рис.3) . Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам  (т.е. свойствам) , не влияющим на основной ключ.

 

 

Отсортированный массив (рис. 2):

 

Массив отсортированный другим методом (рис. 3):

 

Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память.


- Начало -  - Назад -  - Вперед -



Книжный магазин