ГЛАВА 3. СОРТИРОВКА

ГЛАВА 3. СОРТИРОВКА

Сортировкой данных называют перегруппировку заданного одномерного массива объектов в определенном порядке.

В главе рассмотрены некоторые простые методы сортировки, которые принято использовать для сортировки файлов небольшого размера или специальной структуры. Этим методам отдают предпочтение по причине их простой реализации. За некоторым исключением, они не могут быть использованы для сортировки файлов с произвольной организацией и больших размеров, так как время их работы будет чрезмерно большим, даже при запуске алгоритмов на быстродействующих компьютерах.

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

Рассмотренные ниже алгоритмы предназначаются для сортировки одномерных массивов. Под одномерным массивом понимается фиксированный набор данных одного типа, которые хранятся в памяти в виде непрерывного ряда элементов. Доступ к элементам массива осуществляется по индексам. Так, запись вида определяет i-й элемент массива.

В общем случае каждый элемент последовательности может иметь несколько полей. Служащее критерием поиска поле называется ключом сортировки. Часто в качестве ключа выступает число.

Среди алгоритмов сортировки принято выделять адаптивные и неадаптивные. Адаптивные методы сортировки выполняют последовательности операций, основываясь на порядке следования данных в сортируемом массиве. Неадаптивные методы не зависят от последовательности хранения элементов массива.

Одной из важнейших характеристик алгоритма сортировки является время выполнения. В главе приведены оценки времени сортировки в зависимости от числа элементов в массиве N.

Дополнительным фактором эффективности метода можно считать дополнительный объем оперативной памяти, который используется реализующим его алгоритмом. В зависимости от объема этой памяти все методы сортировки можно разделить на три категории:

· Методы сортировки «на месте» или прямые методы сортировки. Этот класс методов не требует выделения дополнительной памяти или требуют выделения незначительного ее объема (например, для хранения стека или таблицы).

· Методы … Такие методы требует выделения памяти для размещения указателей или индексов для обеспечения доступа к элементам массива.

· Методы, требующие выделения дополнительной памяти для хранения копии самого сортируемого массива.

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

Все алгоритмы сортировки реализуют обращение к элементам массива для выполнения одного из двух действий: доступ к ключам элементов целью их сравнения и доступ к самим элементам с целью их перемещения.

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

В зависимости от основного действия, которое реализует метод, принято выделять сортировки основанные на обменах, вставках, выборе и пр. Однако данную классификацию нельзя считать строгой – в зависимости от реализации один и тот же метод сортировки может быть отнесен как к одной, так и к другой группе.

12 3 Следующая ⇒