Таблица – это список, состоящий из конечного множества элементов, при чем каждый элемент характеризуется рядом признаков (свойств). Один из признаков, называемый ключом, позволяет отличить один элемент от другого (идентифицировать элемент). Ключ может однозначно определять элемент таблицы (ключи всех элементов различны) или неоднозначно (в таблице есть элементы с равными ключами).
Неупорядоченная таблица – это таблица, элементы которой располагаются в порядке их поступления в таблицу.
Упорядоченная таблица – это таблица, между элементами которой
установлено отношение порядка. Это отношение, как правило,
устанавливается на признаке ключ. Поэтому говорят, что таблица упорядочена по ключам элементов. Таблица упорядочена по возрастанию значений ключа, если ключ( Ti ) < ключ( Ti+1 ) для всех i = 1, 2 , . . . , n-1
( здесь Ti - i -й элемент таблицы T). Таблица упорядочена по убыванию значений ключа, если ключ( Ti ) > ключ( Ti+1) для всех i = 1, 2, . . . , n-1.
В неупорядоченной таблице поиск элемента в среднем будет выполнен за n/2 сравнений, так как поиск заключается в последовательном просмотре элементов таблицы (максимальное число сравнений n). В упорядоченной таблице кроме последовательного просмотра можно применять бинарный поиск, максимальное число сравнений при котором 1 + log2 n.
Время поиска в хеш-таблице без коллизий постоянно – это время вычисления функции расстановки. Время поиска в таблицах с перемешиванием для метода линейного рехеширования зависит от коэффициента загрузки таблицы k = n/N, среднее число сравнений
e = ( 1 - k/2 ) ( 1 - k).

Далее следует информация, которая возможно пригодиться.

Разрешать коллизии можно в исходной или в дополнительной таблице. Если в исходной, то такая таблица называется таблицей с перемешиванием или с открытой адресацией. Таблица с перемешиванием должна быть инициирована, чтобы элементы таблицы получили в начале значение «пусто» (при взятии элемента из такой таблицы надо различать еще одно состояние: элемент удален из таблицы). В таблицах с перемешиванием применяют линейное (метод последовательных испытаний или проб), случайное или квадратичное рехеширование. Наиболее простой метод - линейное рехеширование, который заключается в том, что функция вторичной расстановки fú определяется как
fú (ключ, i) = ( f (ключ) + i ) mod N ,
здесь значение i равно 1, 2, . . . , а f (ключ) это значение, дающее коллизию. Рехеширование продолжается до тех пор, пока очередная позиция массива с номером fú (ключ, i) не окажется пустой или равной снова своему начальному значению ( в этом случае таблица полна ). Линейное рехеширование применяют, если таблица никогда не бывает полностью заполненной (лучше, если она заполнена не более чем на 70%).
В случае разрешения коллизии в дополнительной таблице удобно использовать хеширование с цепочками. В таких таблицах элементы, которым соответствует одно и то же хеш-значение, связываются в цепочку – список, а в самом элементе таблицы хранится ссылка на список

Выполняется на упорядоченном одномерном массиве. Производит самый быстрый поиск при таких условиях.
Максимальное количество сравнений(проходов) log2n. Работает следующим образом: смотрим середину первоначального интервала - больше, меньше, равна ли искомому значению? Если равна – то искомый элемент найден, если меньше, то делаем новый интервал, который начинается с середины предыдущего интервала и заканчивается той же верхней границей предыдущего, т.е. это вторая половина исходного интервала, далее вся процедура повторяется. Если середина - больше искомого значения, то новый интервал будет первой половиной исходного интервала. И так итеративно сужаем наш интервал до тех пор, пока искомый элемент не будет найден или не дойдем до пустого интервала.

while((low <= high)&&(!found)) {
mid=(low+high)/2;
if(keys[mid] == key) found = 1;
else if(key > keys[mid]) low = mid + 1;
else high = mid - 1;
}
if (found==1) return mid;
if(found==0) {
printf("Record not found!\n");
return -1;
}

Алгоритм Рабина — Карпа

Алгоритм Рабина—Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он не широко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность O(nm), что является одной из причин того, почему он не используется широко. Однако, он имеет уникальную особенность быть способным находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k.

Одно из простейших практических применений алгоритма Рабина—Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах. Затем, алгоритм Рабина—Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для лёгкого избежания расстройства системы из-за небольших изменений, можно игнорировать детали, такие как регистр или пунктуация при помощи их удаления. Поскольку количество строк, которые мы ищем, k, очень большое, обычные алгоритмы поиска одиночных строк неэффективны.

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что не нужно сравнивать шаблон (строка, которую хотим найти) с каждой буквой исходного текста, так как некоторые из них можно пропустить. Чем длиннее шаблон, тем быстрее работает алгоритм.

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

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

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

Алгоритм Кнута — Морриса — Пратта

Этот алгоритм был получен благодаря глубокому анализу алгоритма Морриса-Пратта. Итак, посмотрим, что еще можно сделать, чтобы увеличить размер сдвига.

Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.

При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Более того, если мы хотим избежать выявления другого несовпадения ( то есть не тратить на это операцию сравнения ;-) ), буква, находящаяся за префиксом v в образце должна отличаться от b. Наиболее длинный такой префикс v называется границей u ( он встречается по обоим сторонам u ).

Это приводит к следующему алгоритму: пусть kmp_next[ j ] - длина длиннейшей границы x[ 0, j - 1 ], за которой следует символ c, отличающийся от x[ j ]. Тогда после сдвига мы можем возобновить сравнения между символами y[ i + j ] и x[ j - kmp_next[ j ] ] без возможной потери местонахождения образца. Таблица kmp_next может быть вычислена за O( m ) перед поиском через применение этого же алгоритма поиска к самому образцу ( т.е y = x ). При этом максимальное количество сравнений для одного символа текста - logФ( m ), где Ф - золотое сечение: ( корень из 5 + 1 ) / 2.

Внутреннее упорядочивание оперирует с последовательностями, целиком помещающимися в памяти с произвольным доступом к любой её ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
В современных компьютерах широко применяется подкачка и кэширование памяти. Алгоритм упорядочивания должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешнее упорядочивание оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (дисковые файлы), т.е в данный момент мы "видим" только один элемент. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к особым методам упорядочивания, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем работа с оперативной памятью.
доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим объём данных не позволяет им разместиться в оперативной памяти компьютера.
Принято называть "внешней" сортировкой сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в основную память и применить один из рассмотренных в предыдущем разделе методов внутренней сортировки. Наиболее часто внешняя сортировка применяется в системах управления базами данных при выполнении запросов, и от эффективности применяемых методов существенно зависит производительность СУБД.

Следует пояснить, почему речь идет именно о последовательных файлах, т.е. о файлах, которые можно читать запись за записью в последовательном режиме, а писать можно только после последней записи. Методы внешней сортировки появились, когда наиболее распространенными устройствами внешней памяти были магнитные ленты. Для лент чисто последовательный доступ был абсолютно естественным. Когда произошел переход к запоминающим устройствам с магнитными дисками, обеспечивающими "прямой" доступ к любому блоку информации, казалось, что чисто последовательные файлы потеряли свою актуальность. Однако это ощущение было ошибочным.

В этой и следующей частях книги мы будем обсуждать методы сортировки информации. В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<="). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

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

Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа © и число перестановок элементов (M).

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

Основными операциями, выполняемыми над таблицами, являются упорядочение (сортировка) записей и поиск в таблице записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей таблицы в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ). Существует достаточно много методов сортировки, принципиально отличающихся друг от друга. Если таблица целиком помещается в оперативной памяти ЭВМ,то ее упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются :
С - количество операций сравнения пар ключей,
Р - число перестановок элементов ,
S - резерв памяти.

Среднее количество операций сравнения зависит от метода сортировки и при рациональном выборе метода достигает некоторого минимума,зависящего от n - размера таблицы ( размер таблицы - количество содержащихся в ней записей). Методы внутренней сортировки можно разделить на две группы:
- методы, не требующие резерва памяти;
- методы, требующие резерва памяти.

К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки, метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений. Более сложные алгоритмы обычно обеспечивают получение результата за n*log2(n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в таблице и их предварительной упорядоченности.

Все дело в том, что практически все используемые в настоящее время дисковые устройства снабжены подвижными магнитными головками. При выполнении обмена с дисковым накопителем выполняется подвод головок к нужному цилиндру, выбор нужной головки (дорожки), прокрутка дискового пакета до начала требуемого блока и, наконец, чтение или запись блока. Среди всех этих действий самое большое время занимает подвод головок. Именно это время определяет общее время выполнения операции. Единственным доступным приемом оптимизации доступа к магнитным дискам является как можно более "близкое" расположение на накопителе последовательно адресуемых блоков файла. Но и в этом случае движение головок будет минимизировано только в том случае, когда файл читается или пишется в чисто последовательном режиме. Именно с такими файлами при потребности сортировки работают современные СУБД.

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

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Трудоемкость худшего случая для этих алгоритмов составляет O(n*log(n)), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим
объём данных не позволяет им разместиться в ОЗУ

Пузырьковая сортировка, шейкер-сортировка
Расположим массив сверху вниз, от нулевого элемента - к последнему.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

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

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

template<class T>
void bubbleSort(T a[], long size) {
long i, j;
T x;

for( i=0; i < size; i++) { // i - номер прохода
for( j = size-1; j > i; j-- ) { // внутренний цикл прохода
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
}
}
}
}
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.

Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит ?

Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала !).

Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

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

template<class T>
void shakerSort(T a[], long size) {
long j, k = size-1;
long lb=1, ub = size-1; // границы неотсортированной части массива
T x;

do {
// проход снизу вверх
for( j=ub; j>0; j-- ) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}

lb = k+1;

// проход сверху вниз
for (j=1; j<=ub; j++) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}

ub = k-1;
} while ( lb < ub );
}

Насколько описанные изменения повлияли на эффективность метода ? Среднее количество сравнений, хоть и уменьшилось, но остается O(n2), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.

Сортировка вставками (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

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

typedef int array_type; /* или typedef char array_type;*/

void insertSort(array_type a[], int length) {
int i, j;
array_type value;
for (i = 1; i < length; i++) {
value = a[i];
for (j = i-1; (j >= 0) && (a[j] > value); j--) {
a[j+1] = a[j];
}
a[j+1] = value;
}

Сортировка выбором
Cортировка выбором (англ. selection sort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Шаги алгоритма:
1. находим минимальное значение в текущем списке
2. производим обмен этого значения со значением на первой позиции
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент
Если вы захотите сами изобрести алгоритм сортировки, то вполне вероятно, что вы напишете алгоритм подобный сортировке методом вставок, потому что он, по-видимому, наиболее интуитивно понятный и легко описываемый.
Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения..
C
for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++) {
if (x[min] > x[j]) {
min = j;
}
}
temp = x[i];
x[i] = x[min];
x[min] = temp;
}

Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.
Описание алгоритма
Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.
Пусть n — длина исходного массива, k — максимальное число в массиве.
Тогда временная сложность алгоритма равна O(n+k), а ёмкостная — O(n+k).
Можно работать и с массивом целых чисел, все элементы которого принадлежат указанному диапазону от min до max. Для оценки сложности получим k = max - min + 1.
C
void CountingSort (int *a, int n, int min, int max)
{
int i, j, c;
int *b;
assert(n > 0);
assert(min <= max);
b = (int *)calloc(max - min + 1, sizeof(int));
assert(b != NULL);
for (i = 0; i <= n - 1; ++i) ++b[a[i] - min];
for (j = min; j <= max; ++j)
{
c = b[j - min];
while (c > 0)
{
*a = j; ++a; --c;
}
}
free(b);
}

Соpтиpовка Шелла. Это еще одна модификация пyзыpьковой соpтиpовки. Сyть ее состоит в том, что здесь выполняется сpавнение ключей, отстоящих один от дpyгого на некотоpом pасстоянии d. Исходный pазмеp d обычно выбиpается соизмеpимым с половиной общего pазмеpа соpтиpyемой последовательности. Выполняется пyзыpьковая соpтиpовка с интеpвалом сpавнения d. Затем величина d yменьшается вдвое и вновь выполняется пyзыpьковая соpтиpовка, далее d yменьшается еще вдвое и т.д. Последняя пyзыpьковая соpтиpовка выполняется пpи d=1. Качественный поpядок соpтиpовки Шелла остается O(N^2), сpеднее же число сpавнений, опpеделенное эмпиpическим пyтем - log2(N)^2*N. Ускоpение достигается за счет того, что выявленные "не на месте" элементы пpи d>1, быстpее "всплывают" на свои места.
[править] C++
template <class T>
void Shell_sort( T a[], const int n )
{
for(int step = n/2 ; step>0 ; step >>= 1){
for( int i=0; i<(n-step); ++i ){
int j = i;
while ( (j>=0) && (a[j]>a[j+step]) ){
T tmp = a[j];
a[j] = a[j+step];
a[j+step] = tmp;
--j;
}
}
}
}

Итак, мы постепенно переходим от более-менее простых к сложным, но эффективным методам. Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).

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

Пример действий для массива a[0]... a[7]:

44 55 12 42 94 18 06 67 исходный массив
44 55 12 42 67 18 06 |94 94 <-> 67
44 55 12 42 06 18 |67 94 67 <-> 06
44 18 12 42 06 |55 67 94 55 <-> 18
06 18 12 42 |44 55 67 94 44 <-> 06
06 18 12 |42 44 55 67 94 42 <-> 42
06 12 |18 42 44 55 67 94 18 <-> 12
06 |12 18 42 44 55 67 94 12 <-> 12

Вертикальной чертой отмечена левая граница уже отсортированной(правой) части массива.

Рассмотрим оценку количества операций подробнее.
Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]..a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности, поэтому необходимое на него время: O(n). Итак, n шагов по O(n) каждый - это O(n2).

Произведем усовершенствование: построим структуру данных, позволяющую выбирать максимальный элемент последовательности не за O(n), а за O(logn) времени. Тогда общее быстродействие сортировки будет n*O(logn) = O(n log n).

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

Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором

* все узлы имеют глубину k или k-1 - дерево сбалансированное.
* при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид:
* выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю.

Как хранить пирамиду? Наименее хлопотно - поместить ее в массив.

Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме:

* в a[0] хранится корень дерева
* левый и правый сыновья элемента a[i] хранятся, соответственнно, в a[2i+1] и a[2i+2]

Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2].

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

* никаких дополнительных переменных, нужно лишь понимать схему.
* узлы хранятся от вершины и далее вниз, уровень за уровнем.
* узлы одного уровня хранятся в массиве слева направо.

Запишем в виде массива пирамиду.. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42.

Восстановить пирамиду из массива как геометрический объект легко - достаточно вспомнить схему хранения и нарисовать, начиная от корня.

Фаза 1 сортировки: построение пирамиды

Hачать построение пирамиды можно с a[k]...a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i,j: i = 2i+1 ( или j = 2i+2 )... Просто потому, что такие i,j находятся за границей массива.

Следует заметить, что неправильно говорить о том, что a[k]..a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]...a[n].

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

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]..a[n] на элемент a[i] влево:

1. Смотрим на сыновей слева и справа - в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.
2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.

Новый элемент "просеивается" сквозь пирамиду.

template
void downHeap(T a[], long k, long n) {
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
T new_elem;
long child;
new_elem = a[k];

while(k <= n/2) { // пока у a[k] есть дети
child = 2*k;
// выбираем большего сына
if( child < n && a[child] < a[child+1] )
child++;
if( new_elem >= a[child] ) break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}

Учитывая, что высота пирамиды h <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:

// вызвать downheap O(n) раз для преобразования массива в пирамиду целиком
for(i=size/2; i >= 0; i--) downHeap(a, i, size-1);

Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:

44 55 12 42 // 94 18 06 67 Справа - часть массива, удовлетворяющая
44 55 12 // 67 94 18 06 42 свойству пирамиды,
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.

В геометрической интерпретации ключи из начального отрезка a[size/2]...a[n] является листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так - пока не будет построена вся пирамида.

На рисунках ниже изображен процесс построения. Неготовая часть пирамиды (начало массива) окрашена в белый цвет, удовлетворяющий свойству пирамиды конец массива - в темный.

Фаза 2: собственно сортировка

Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:

1. Берем верхний элемент пирамиды a[0]...a[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив a[0]...a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.
2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.

Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.

94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки
67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94

Код внешней процедуры сортировки:

template
void heapSort(T a[], long size) {
long i;
T temp;

// строим пирамиду
for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);

// теперь a[0]...a[size-1] пирамида

for(i=size-1; i > 0; i--) {
// меняем первый с последним
temp=a[i]; a[i]=a[0]; a[0]=temp;

// восстанавливаем пирамидальность a[0]...a[i-1]
downHeap(a, 0, i-1);
}
}

Каково быстродействие получившегося алгоритма ?

Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Пирамидальная сортировка не использует дополнительной памяти.

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

Поведение неестественно: частичная упорядоченность массива никак не учитывается.

Быстрая сортировка
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Самый быстрый из известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов).
Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать либо средний по положению элемент (элемент с индексом [n/2], тогда алгоритм будет работать за время O(n log n) в худшем случае), либо элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
1. два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
2. вычисляется опорный элемент m;
3. индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;
4. индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
5. если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
6. если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.
Оценка эффективности
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате самый эффективный улучшенный метод.
• Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N. Это дало бы наименьшее время сортировки.
• Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.
• Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
[править] Достоинства и недостатки
Достоинства:
• Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных.
• Простая реализация.
• Хорошо сочетается с алгоритмами кэширования и подкачки памяти.
• Хорошо работает на «почти отсортированных» данных — если исходный массив уже близок к отсортированному, алгоритм не приводит к излишним перестановкам уже стоящих в правильном порядке элементов.
Недостатки:
• При классической реализации требует в худшем случае много дополнительной памяти. Правда, вероятность возникновения худшего случая ничтожна.
• Неустойчив — если требуется устойчивость, приходится расширять ключ.
C
Первый вариант Работает для любых чисел
int partition (mytype * m, int a, int b)
{
int i = a;
for (int j = a; j <= b; j++) // просматриваем с a по b
{
if (m[j] <= m[b]) // если элемент a[j] не превосходит a[b],
{
swap(m[i], m[j]); // меняем местами a[j] и a[a], a[a+1], a[a+2] и так далее...
// то есть переносим элементы меньшие a[b] в начало, а затем и сам a[b] «сверху»
i++; // таким образом последний обмен: a[b] и a[i], после чего i++
}
}
return i-1; // в индексе i хранится <новая позиция элемента a[b]> + 1
}

void quicksort (mytype * m, int a, int b) // a - начало подмножества, b - конец
{ // для первого вызова: a = 0, b = <элементов в массиве> - 1
if (a >= b) return;
int c = partition (m, a, b);
quicksort (m, a, c-1);
quicksort (m, c+1, b);
}

При использовании рекурсивного кода, быстрая сортировка будет означать n вложенных рекурсивных вызовов функции quickSort. Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям. Для исключения подобной ситуации можно заменить рекурсию на итерации, реализовав стек на основе массива. Процедура разделения будет выполняться в виде цикла. Каждый раз, когда массив делится на две части, в стек будет направляться запрос на сортировку большей из них, а меньшая будет обрабатываться на следующей итерации. Запросы будут выбираться из стека по мере освобождения процедуры разделения от текущих задач. Сортировка заканчивает свою работу, когда запросы кончаются.
Псевдокод.
Итеративная QuickSort (массив a, размер size) {
Положить в стек запрос на сортировку массива от 0 до size-1.

do {
Взять границы lb и ub текущего массива из стека.
do {
1. Произвести операцию разделения над текущим массивом a[lb..ub].
2. Отправить границы большей из получившихся частей в стек.
3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
} пока меньшая часть состоит из двух или более элементов
} пока в стеке есть запросы
}
Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стека

template<class T>
void qSortI(T a[], long size) {
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
T pivot; // опорный элемент
T temp;
lbstack[1] = 0;
ubstack[1] = size-1;
do {
// Взять границы lb и ub текущего массива из стека.
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
do {
// Шаг 1. Разделение по элементу pivot
ppos = ( lb + ub ) >> 1;
i = lb; j = ub; pivot = a[ppos];
do {
while ( a[i] < pivot ) i++;
while ( pivot < a[j] ) j--;
if ( i <= j ) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i <= j );
// Сейчас указатель i указывает на начало правого подмассива,
// j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
// Возможен случай, когда указатель i или j выходит за границу массива
// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
if ( i < ppos ) { // правая часть больше
if ( i < ub ) { // если в ней больше 1 элемента - нужно
stackpos++; // сортировать, запрос в стек
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j; // следующая итерация разделения
// будет работать с левой частью
} else { // левая часть больше
if ( j > lb ) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while ( lb < ub ); // пока в меньшей части более 1 элемента
} while ( stackpos != 0 ); // пока есть запросы в стеке
}
Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели quickSort. А именно, вместо разделения по опорному элементу массив просто делится пополам.
// a - сортируемый массив, его левая граница lb, правая граница ub
template
void mergeSort(T a[], long lb, long ub) {
long split; // индекс, по которому делим массив

if (lb < ub) { // если есть более 1 элемента

split = (lb + ub)/2;

mergeSort(a, lb, split); // сортировать левую половину
mergeSort(a, split+1, last);// сортировать правую половину
merge(a, lb, split, ub); // слить результаты в общий массив
}
}

Функция merge на месте двух упорядоченных массивов a[lb]...a[split] и a[split+1]...a[ub] создает единый упорядоченный массив a[lb]...a[ub].

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

Один из способов состоит в слиянии двух упорядоченных последовательностей при помощи вспомогательного буфера, равного по размеру общему количеству имеющихся в них элементов. Элементы последовательностей будут перемещаться в этот буфер по одному за шаг.
merge ( упорядоченные последовательности A, B , буфер C ) {
пока A и B непусты {
cравнить первые элементы A и B
переместить наименьший в буфер
}
если в одной из последовательностей еще есть элементы
дописать их в конец буфера, сохраняя имеющийся порядок
}

Результатом является упорядоченная последовательность, находящаяся в буфере. Каждая операция слияния требует n пересылок и n сравнений, где n - общее число элементов, так что время слияния: Theta(n).
template
void merge(T a[], long lb, long split, long ub) {
// Слияние упорядоченных частей массива в буфер temp
// с дальнейшим переносом содержимого temp в a[lb]...a[ub]

// текущая позиция чтения из первой последовательности a[lb]...a[split]
long pos1=lb;

// текущая позиция чтения из второй последовательности a[split+1]...a[ub]
long pos2=split+1;

// текущая позиция записи в temp
long pos3=0;

T *temp = new T[ub-lb+1];

// идет слияние, пока есть хоть один элемент в каждой последовательности
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] < a[pos2])
temp[pos3++] = a[pos1++];
else
temp[pos3++] = a[pos2++];
}

// одна последовательность закончилась -
// копировать остаток другой в конец буфера
while (pos2 <= ub) // пока вторая последовательность непуста
temp[pos3++] = a[pos2++];
while (pos1 <= split) // пока первая последовательность непуста
temp[pos3++] = a[pos1++];

// скопировать буфер temp в a[lb]...a[ub]
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];

delete temp[ub-lb+1];
}

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

В случае прямого слияния мы не получаем никакого преимущества, если данные уже
являются частично упорядоченными. Размер сливаемых при каждом проходе
последовательностей не зависит от существования более длинных уже упорядоченных
последовательностей, которые можно было бы просто объединить.
Сортировка, при которой всегда сливаются две самые длинные из возможных
последовательностей, назвается естественным слиянием.
Эта сортировка является двухфазной сортировкой слиянием с тремя
лентами(файлами).
Максимальную упорядоченную последовательность будем называть серией.
Пусть имеется начальный файл А. Каждый проход состоит из фазы распределения
серий из фалйа А поровну в файлы В и С и фазы слияния, объединяющей серии из
файлов В и С в файл А.
Процесс сортировки заканчивается, как только в файле А останется только одна
серия.
Рассмотрим сортировку естественным слиянием на примере (серии подчеркнуты).
Пусть задан файл А:

А - 17 31 05 59 13 41 43 76 11 23 29 47 03 07 71 02 19 57 37
61

B - 17 31 13 41 43 76 03 07 71 37 61

C - 05 59 11 23 29 47 02 19 57

A - 05 17 31 59 11 13 23 29 41 43 47 76 02 03 07 19 57 71 37 61

B - 05 17 31 59 02 03 07 19 57 71

C - 11 13 23 29 41 43 47 76 37 61

A - 05 11 13 17 23 29 31 41 43 47 59 76 02 03 07 19 37 57 61 71

B - 05 11 13 17 23 29 31 41 43 47 59 76

C - 02 03 07 19 37 57 61 71

A - 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57 59 61 71 76
Hа основе рассмотренного выше алгоритма легко получить алгоритм однофазной
сортировки естественным слиянием с четырьмя файлами.

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

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

*********** сортировка с помощью двоичного дерева *************/
#include
#include
typedef struct tree
{
int a; // данные
struct tree *left; // левый сын
struct tree *right; // правый сын

} TREE;

TREE *add_to_tree(TREE *root, int new_value)
{
if (root==NULL) // если нет сыновей - создаем новый элемент
{
root = (TREE*)malloc(sizeof(TREE));
root->a = new_value;
root->left = root->right = 0;
return root;
}
if (root->a < new_value) // добавлем ветвь
root->right = add_to_tree(root->right, new_value);
else
root->left = add_to_tree(root->left, new_value);
return root;
}

void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
{
static max2=0; // счетчик элементов нового массива
if (root==NULL) return; // условие окончания - нет сыновей
tree_to_array(root->left, a); // обход левого поддерева
a[max2++] = root->a;
tree_to_array(root->right, a); // обход правого поддерева
free(root);
}

void sort_tree(int a[], int elem_total) // собственно сортировка
{
TREE *root;
int i;
root = NULL;
for (i=0; i < max; i++)
root = add_to_tree(root, a[i]);
tree_to_array(root, a); // заполнение массива
}
/* тестовая программа */

void main() {
int i;
/* Это будем сортировать */
int a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
sort_tree(a, 14);

printf("sorted array:\n");
for (i=0;i<14;i++) printf("%d ",a[i]);
}