СОРТИРОВКА И ПОИСК
Простейшая сортировка. Если попросить не знающих содержаниеэтого раздела написать функцию, выполняющую упорядочениеданных в массиве, то 90 процентов напишут примерно так:
// Дилетантская сортировка
voidsort(int А[], int n){
for (int i=0; i<n; i++)
for (int j = i; j<n; j++)
if (A[i]>A[j]){
int c=A[i]; A[i]=A[j]; A[j]=c;}
}
В основе лежит логика «здравого смысла». Необходимо переставлятьэлементы массива, если они нарушают порядок, количествотаких перестановок должно соответствовать количеству возможныхпар элементов, а это дает цикл в цикле. Принцип сравнения
«каждый с каждым» приводит к тому, что для каждого i-roэлемента необходимо просмотреть все последующие за ним (второйцикл начинается с j=i). И наконец, программа отражает справедливуюубежденность большинства, что за один цикл просмотраупорядочить массив нельзя.Первый парадокс: несмотря на явное наличие обмена, эта сортировкаотносится к группе сортировок выбором.
Линейный поиск. Для начала зададимся жизненно важнымвопросом: а зачем вообще нужна сортировка? Ответ простой: еслиданные не упорядочены, то найти что-либо, нас интересующее,можно только последовательным перебором всех элементов. Для
обычного массива фрагмент программы, определяющий, имеет лиодин из его элементов заданное значение, выглядит так:
for (i = 0; i<n; i++)
if (A[i] = = B) break;
if (i != n) ...найден...
To, что мы получаем в данном фрагменте только факт наличияэлемента массива с данным значением, не играет никакой роли дляпонимания сущности поиска данных. В реальных программах«элементами массива» являются, конечно, не простые переменные,
а более сложные образования (например, структурированные переменные).
Та часть элемента данных, которая идентифицируетего и используется для поиска, называется ключом. Остальнаячасть несет в себе содержательную информацию, которая извлекаетсяи используется из найденного элемента данных.
Ключ - часть элемента данных, которая используется для егоидентификации и поиска среди множества других таких элементов.Приведенный фрагмент программы обеспечивает в неупорядоченноммассиве последовательный, или линейный, поиск, а
среднее количество просмотренных элементов для массива размерности
N будет равно N/2.
Проверка упорядоченности. Функция проверки упорядоченностимассива служит живой иллюстрацией теоремы: массив упорядочен,если упорядочена любая пара соседних элементов.
/ / — Проверка упорядоченности массива
Intis_sorted(int а[], int n){
for (int i=0; i<n-1; i++)
if (a[i]>a[i + 1]) return 0;
return 1;}
Двоичный поиск в упорядоченных данных. Если элементыданных упорядочены, то найти интересующий нас можно значительнобыстрее. Алгоритм двоичного, или бинарного, поиска основанна делении пополам текущего интервала поиска. В основе
его лежит тот факт, что при однократном сравнении искомого элемента
и некоторого элемента массива мы можем определить, справаили слева от текущего следует искать. Проще всего выбиратьэлемент на середине интервала, в котором производится поиск.Тогда получим такой алгоритм:
- искомый интервал поиска делится пополам, и по значению
элемента массива в точке деления определяется, в какой части следует
искать значение на следующем шаге цикла;
- для выбранного интервала поиск повторяется;
- при «сжатии» интервала в О поиск прекращается;
- в качестве начального интервала выбирается весь массив.
// 25-03.срр
// Двоичньт поиск в упорядоченном массиве
Intbinary(int с[], int n, intval){// Возвращает индекс найденного
Inta,b,m; // Левая, правая границы и
for(a=0,b=n-1; а <= Ь;) { // середина
m = (а + Ь)/2; // Середина интервала
if (c[m] == val) // Значение найдено
return m; // вернуть индекс найденного
if (c[nn] >val)
b = m-1; // Выбрать левую половину
else
а = m + 1; } // Выбрать правую половину
return - 1 ; } // Значение не найдено
Оценим количество сравнений, которые необходимо для поискатребуемого значения. Так как после первого сравнения интервалуменьшается в 2, после второго - в 4 раза и т.д., то количествосравнений будет не больше соответствующей степени 2, дающейразмерность массива п, или 2^ = п, тогда s = log2(n).
Для массива из 1000 элементов их будет 10, из 1 000 000 - 20.
Именно ради этого и существуют многочисленные алгоритмы сортировки.С небольшими изменениями данный алгоритм может использоватьсядля определения места включения нового значенияв упорядоченный массив. Для этого необходимо ограничить деление
интервала до получения единственного элемента (а=Ь), после чегодополнительно проверить, куда следует производить включение.
// Двоичный поиск места включения в упорядоченном массиве
Intfind(lnt с[], int n, intval){
Inta,b,m; // Левая, правая границы и
for(a=0,b=n-1; а < b;) { // середина
m = (а + b)/2; // Середина интервала
if (c[m] == val) // Значение найдено -
return m; // вернуть индекс
if (c[m] >val)
ID = m-1; // Выбрать левую половину
else
a = m + 1; // Выбрать правую половину
} // Выход по a==b
if (val> c[a]) return a+1; // Включить на следующую
return a; } // или на текущую позицию
Трудоемкость алгоритмов. Для сравнения свойств алгоритмовважно не то, сколько конкретно времени они выполняются наданных известного объема, а как они поведут себя при увеличенииэтого объема в 10, 100, 1000 раз и т.д., то есть тенденция увеличения
времени обработки, а оно в свою очередь зависит от количествабазовых операций над элементами данных - выборок, сравнений,перестановок. С этой целью введено понятие трудоемкости.
Трудоемкость - зависимость числа базовых операций алгоритма от размерности входных данных.Трудоемкость показывает не абсолютные затраты времени всекундах или минутах, что зависит от конкретных особенностейкомпьютера, а в какой зависимости растет время выполнения программыпри увеличении объемов обрабатываемых данных. Оценимтрудоемкости известных нам алгоритмов (рис. 2.6):
- трудоемкость линейного поиска - N/2 - линейная зависимость;
- трудоемкость двоичного поиска - зависимость логарифмическаяlog2N ;
- для сортировки обычно используется цикл в цикле. Отсюдавидно, что трудоемкость даже самой плохой сортировки не можетбыть больше NxN. - зависимость квадратичная. За счет оптимизацииона может быть снижена до Nxlog(N);
- алгоритмы рекурсивного поиска, основанные на полном переборе
вариантов (см. раздел 3.4), имеют обычно показательную
зависимость трудоемкости от размерности входных данных (т^).
Классификация сортировок. Алгоритмы сортировки можноклассифицировать по нескольким признакам.
Вид сортировки по размещению элементов: внутренняя – впамяти, внешняя - в файле данных.
Вид сортировки по виду структуры данных, содержащей сортируемыеэлементы: сортировка массивов, массивов указателей,списков и других структур данных.
Основная идея алгоритма. В основе многообразия сортировоклежит многообразие идей. Здесь нужно сразу же отделить «зернаот плевел»: идею алгоритма от вариантов ее технической реализации,которых может быть несколько, а также от улучшений основногометода. Кроме того, применительно к разным структурамданных один и тот же алгоритм сортировки будет выглядеть по-разному. Еще более запутывает вопрос использование одной и тойже идеи на основной и второстепенной ролях. Например, обмензначений соседей, положенный в основу обменных сортировок,используется в сортировке вставками, именуемой «сортировка погружением». Попробуем навести здесь порядок.
Прежде всего, выделим сортировки, в которых в процессе работысоздаетсяупорядоченная часть - размер ее увеличиваетсяна 1 за каждый шаг внешнего цикла. Сюда относятся две группысортировок:
сортировка вставками: очередной элемент помещается по местусвоего расположения в выходную последовательность (массив);
сортировка выбором: выбирается очередной минимальныйэлемент и помещается в конец последовательности.
Две другие группы используют разделения на части, но по различнымпринципам и с различной целью:
сортировка разделением: последовательность (массив) разделяетсяна две частично упорядоченные части по принципу «больше-меньше», которые затем могут быть отсортированы независимо(в том числе тем же самым алгоритмом);
сортировка слиянием: последовательность регулярно распределяетсяв несколько независимых частей, которые затем объединяются(слияние).
Сортировки этих групп отличаются от «банальных сортировок»тем, что процесс упорядочения в них в явном виде не просматривается(сортировка без сортировки).
Отдельная группа обменных сортировок с многочисленнымиоптимизациями основана на идее регулярного обмена соседнихэлементов.
Особняком стоит сортировка подсчетом. В ней определяется
количество элементов, больших или меньших данного, определяется
его местоположение в выходном массиве.
СТАНДАРТНЫЕ ПРОГРАММНЫЕ РЕШЕНИЯ
Сортировка выбором. На каждом шаге сортировки из последовательностивыбирается минимальный элемент и переносится вконец выходной последовательности. Дальше вступают в силу деталипроцесса, но характерным остается наличие двух независимых
частей - неупорядоченной (оставшихся элементов) и упорядоченной.
При исключении выбранного элемента из массива наего место может быть записано «очень большое число», исключающееего повторный выбор. Выбранный элемент может удалятсяпутем сдвига оставшейся части, минимальный элемент может меняться
местами с «очередным». Трудоемкость алгоритма - nxii/2.
Следующий пример - один из многочисленных вариантов«мирного сосуществования» упорядоченной и неупорядоченнойчастей в одном массиве. Упорядоченная часть находится слева, иее размерность соответствует числу выполненных шагов внешнего
цикла. Неупорядоченная часть расположена справа, поэтому поискминимума с запоминанием индекса минимального элемента происходитв интервале от i до конца массива.
/ / — Сортировка выбором