Структуры и алгоритмы обработки данных
Уже на примере сортировки пронумерованных
Уже на примере сортировки пронумерованных карточек становится очевидным существенное различие в этих подходах. Если карты "выстроены" в виде массива, то они как бы лежат перед сортирующим, он видит каждую из них и имеет к ней доступ. Если же карты образуют файл, то это предполагает, что видна только верхняя карта в каждой из стопок. Такое ограничение, конечно же, серьезно повлияет на метод сортировки, но ничего не поделаешь: ведь карточек может быть так много, что все они на столе не поместятся.
Прежде чем идти дальше, введем некоторые понятия и обозначения. Ими мы будем пользоваться далее. Если у нас есть элементы а1, а2,..., аn, то сортировка есть перестановка этих элементов массив ак1, ак2, ..., акn, где при некоторой упорядочивающей функции f выполняются отношения f аk1 <= f аk2 <= ... <= f аkn.
Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента поля каждого элемента. Ее значение называется ключом кеу элемента. Поэтому для представления элементов хорошо подходят такие образования, как запись, а графически это представляется так (рис. 1):
Говоря об алгоритмах сортировки, мы будем обращать внимание лишь на компоненту - ключ, другие же компоненты можно даже и не определять (рис.2). Поэтому из наших дальнейших рассмотрений вся сопутствующая информация. Чтобы уменьшить эти затраты, сортировку производят в таблице адресов ключей. После сортировки перестанавливают указатели. Это метод сортировки таблицы адресов (рис.3) . Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам (т.е. свойствам) , не влияющим на основной ключ.
Отсортированный массив (рис. 2):
Массив отсортированный другим методом (рис. 3):
Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий