Сортировки и поиск

В разделе описываются основные алгоритмы сортировкистатических массивов.

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

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы уже упорядочены по одному ключу, а сортировка ведется по другому ключу.

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов необходимо выполнять in situ (на том же месте). Поэтому при выборе метода сортировки необходимо установить критерий эффективности, то есть определить ее быстродействие. При сортировке элементов в массиве выполняются два действия: сравнения элементов по некоторому ключу и пересылка элементов. И число сравнений (C), и число перестановок (M) зависят от размерности массива N.

Хорошие алгоритмы сортировки требуют порядка N*logN сравнений, более простые – порядка N² сравнений ключей. Хотя в более сложных алгоритмах меньше операций, сами эти операции более сложны; поэтому при достаточно малых N простые методы работают быстрее, но их не следует использовать при больших N.

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

q Исходная упорядоченность входного множества: во входном множестве могут попадаться упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе. Говорят, что сортировка демонстрирует естественное поведение, если C и M имеют наименьшие значения из возможных в случае упорядоченного массива и возрастают с ростом неупорядоченности, и неестественное поведение в противном случае.

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

Методы сортировки массива можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1. Сортировка выбором
2. Сортировка включениями
3. Сортировка обменом

Во всех программных примерах используются данные, определенные так:

q const N=… – целое положительное число, число элементов в массиве;

q type TData = array[1..N] of integer – сортируемые последовательности.

Результатом сортировки является массив, элементы которого упорядочены по возрастанию ключа. Для простоты ключом элемента считается значение самого элемента.