4.6. Сортировка и поиск
«Далее он расставил всех присутствующих
по этому кругу (строго как попало)».
Льюис Кэрролл.
Алиса в стране чудес (Перевод Бориса Заходера)
Раздел «Сортировка и поиск» важен по нескольким причинам. Во-первых, он касается свойств упорядоченных и неупорядоченных данных. Кроме того, нигде больше Вы не найдете такого разнообразия решений одной и той же задачи.
Поиск и упорядочение Линейный поиск. Для начала зададимся жизненно важным вопросом: а зачем вообще нужна сортировка? Ответ простой: если данные не упорядочены, то найти что-либо нас интересующее можно только путем последовательного перебора всех элементов (если не полагаться на удачу и судьбу, см., например, хэширование – 6.6). Для обычного массива фрагмент программы, определяющий, имеет ли один из его элементов заданное значение, выглядит так:
for (i = 0; i < n; i++)
if (A[i] == B) break;
if (i != n)...найден...То, что мы получаем в данном фрагменте только факт наличия элемента массива с данным значением, не играет никакой роли для понимания сущности поиска данных. В реальных программах «элементами массива» являются, конечно, не простые переменные, а более сложные образования (например, структурированные переменные). Та часть элемента данных, которая идентифицирует его и используется для поиска, называется ключом. Остальная часть несет в себе содержательную информацию, которая извлекается и используется из найденного элемента данных.
Поиск значения путем последовательного перебора всех элементов называется линейным поиском. Его трудоемкость в среднем Tср(N)=N/2 => O(N). По статистике надо просмотреть половину последовательности (по «закону подлости» - всю).
Двоичный поиск в упорядоченных данных. Если данные упорядочены, то найти интересующий нас можно значительно быстрее. Алгоритм двоичного или бинарного поиска основан на делении пополам текущего интервала поиска. В основе его лежит тот факт, что при однократном сравнении искомого элемента и некоторого элемента массива мы можем определить, справа или слева от текущего следует искать. Проще всего выбирать элемент на середине интервала, в котором производится поиск. Основные идеи такого алгоритма:
искомый интервал поиска делится пополам и по значению элемента массива в точке деления определяется, в какой части следует искать значение на следующем шаге цикла;
для выбранного интервала поиск повторяется;
при «сжатии» интервала в 0 поиск прекращается;
в качестве начального интервала выбирается весь массив.
//------------------------------------------------------46-01.cpp
//------Двоичный поиск в упорядоченном массиве
int binary(int c[], int n, int val) { // Возвращает индекс найденного
int a, b, m; // Левая, правая границы и
for (a = 0, b = n - 1; a <= b;) { // середина
m = (a + b) / 2; // Середина интервала
if (c[m] == val) // Значение найдено -
return m; // вернуть индекс найденного
if (c[m] > val)
b = m - 1; // Выбрать левую половину
else
a = m + 1; // Выбрать правую половину
}
return -1;
} // Значение не найденоВ соответствии с принципом удвоения (деления пополам), изложенного в 4.1, алгоритм имеет гарантированную логарифмическую трудоемкость Tmax=log2(N). Именно из-за этого свойства двоичного поиска и существуют многочисленные алгоритмы сортировки. С небольшими изменениями алгоритм может использоваться для определения места включения нового значения в упорядоченный массив. Для этого необходимо ограничить деление интервала до получения единственного элемента (a==b), после чего дополнительно скорректировать место включения.
//------------------------------------------------------46-02.cpp
//------Двоичный поиск места включения в упорядоченном массиве
int find(int c[], int n, int val) {
int a, b, m; // Левая, правая границы и
for (a = 0, b = n - 1; a < b;) { // середина
m = (a + b) / 2; // Середина интервала
if (c[m] == val) // Значение найдено -
return m; // вернуть индекс
if (c[m] > val)
b = m - 1; // Выбрать левую половину
else
a = m + 1; // Выбрать правую половину
} // Выход из цикла по a==b
if (val > c[a]) return a + 1; // Включить на следующую
return a;
} // или на текущую позицию Классификация сортировок
Любая классификация, как известно, неполна и ущербна. Признаками классификации могут быть структуры данных, используемые при сортировке (массивы, списки, деревья), местонахождение данных – в памяти (внутренняя) и в файлах (внешняя). Но все же самым лучшим принципом классификации является классификация идей, на которых строятся сортировки.
сортировки, основанные на наличии упорядоченной и неупорядоченной последовательностей, за один шаг переносят по одному элементу из неупорядоченной части в упорядоченную (перенос). Эта общая идея в зависимости от того, при работе с какой частью массива она проявляет свой «интеллект», дает нам сортировки выбором и вставками. Сюда же относятся вставка погружением и сортировка Шелла, основанная на переменном шаге погружения;
идея обменной сортировки очевидна: если достаточно долго менять местами пары соседних элементов, не находящихся в порядке возрастания, то рано или поздно последовательность упорядочится. Различные оптимизации (шейкер-сортировка, сортировка Шелла) учитывают различные эффекты, возникающие в этом процессе;
распределение предполагает, что элементы исходной последовательности «разбрасываются» (распределяются) - в несколько последовательностей или на различные позиции в одной. Куда помещать очередной элемент, зависит не от его значения, а от его косвенных характеристик. Строго говоря, они и определяют индекс (номер) выходной последовательности или индекс (место) в выходном массиве;
сортировки на основе разделения/слияния основаны на перенесении данных из одной группы в несколько (в простейшем случае – в две) (разделение) и в обратном их соединении (слияние). В отличие от распределения оба процесса линейны, то есть перенос элементов происходит линейно (последовательно). Однако «интеллект» сортировки, т.е. выбор последовательности, в которую или из которой следует помещать элементы, сосредоточен в одном из этих процессов. Тогда другой носит чисто формальный характер разъединения или соединения частей. Поэтому известны сортировки разделением («быстрая», рекурсивное и поразрядное разделение), основанные на разделении массива относительно среднего значения – медианы (см. 2.4) и сортировки слиянием упорядоченных последовательностей (см. там же) – однократное, циклическое, рекурсивное слияние. Более подробно рекурсивных сортировках см. 7.2 и 10.1.
и, наконец, известны сортировки, основанные на хранении данных в ветвящихся последовательностях (или деревьях). Хотя для них обычно используются специальные способы представления (см.8.1,8.4,8.5), их также можно «отобразить» в обычные массивы.
Другим важным критерием, по которому разделяются сортировки, является их эффективность (трудоемкость). Здесь можно выделить несколько групп:
заведомо неэффективные сортировки – это, как правило, простые алгоритмы, основанные на двойном (сложенном) цикле, для которых оценка трудоемкости имеет вид O(N2) – это сортировки выбором, вставками, погружением, обменом, подсчетом. Путем частичных усовершенствований трудоемкость может быть снижена, например, в обменной сортировке Шелла до O(N3/2);
эффективные сортировки, основанные на наличии процесса удвоения или деления пополам при обработке каждого элемента имеют нижнее значение трудоемкости O(Nlog2(N)). Грубое обоснование – процесс удвоения/деления пополам для каждого элемента имеет log2(N) шагов, а элементов всего N. К этой группе относятся все сортировки, основанные на использовании деревьев, слияние и разделение (кроме однократного слияния). Среди них есть как нечувствительные к данным, так и такие, у которых при определенных наборах данных трудоемкость межет возрасти до O(N2) («быстрая», поразрядное и рекурсивное разделение, сортировка на двоичном дереве);
и, наконец, сортировки, использующие дополнительную память, могут иметь качественно другие характеристики трудоемкости, вплоть до линейной T(N)=2(D+N), T(N)=k*N => O(N) (распределяющий подсчет, лексикографическая, поразрядное распределение).
Сортировки выбором и вставками «Дилетантская» сортировка. Если попросить не знающего содержание этого раздела написать функцию, выполняющую упорядочение данных в массиве, то 90% напишут примерно так.
//-------------------------------------------------------------------46-03.cpp
//------ Дилетантская сортировка
void sort(int A[], 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-го элемента необходимо просмотреть все последующие за ним (второй цикл начинается с j=i). И наконец, программа отражает справедливую убежденность большинства, что за один цикл просмотра упорядочить массив нельзя.
Парадокс: несмотря на явное наличие обмена, эта сортировка относится к группе сортировок выбором.
Проверка упорядоченности. Функция проверки упорядоченности массива является живой иллюстрацией теоремы: массив упорядочен, если упорядочена любая пара соседних элементов.
//------------------------------------------------------46-04.cpp
//---- Проверка упорядоченности массива
int is_sorted(int a[], int n) {
for (int i = 0; i < n - 1; i++)
if (a[i] > a[i + 1]) return 0;
return 1;
}Сортировка выбором. На каждом шаге сортировки из последовательности выбирается минимальный элемент и переносится в конец выходной последовательности. Дальше вступают в силу детали процесса, но характерным остается наличие двух независимых частей – неупорядоченной (оставшихся элементов) и упорядоченной. При исключении выбранного элемента из массива на его место может быть записано «очень большое число», исключающее его повторный выбор. Выбранный элемент может удаляться путем сдвига оставшейся части, минимальный элемент может меняться местами с очередным.
Следующий пример – один из многочисленных вариантов «мирного сосуществования» упорядоченной и неупорядоченной частей в одном массиве. Упорядоченная часть находится слева и ее размерность соответствует числу выполненных шагов внешнего цикла. Неупорядоченная часть расположена справа, поэтому поиск минимума с запоминанием индекса минимального элемента происходит в интервале от i-го до конца массива.
//------------------------------------------------------46-05.cpp
//---- Сортировка выбором
void sort(int in[], int n){
for ( int i=0; i < n-1; i++){ // Для очередного i
for ( int j=i+1, k=i; j<n; j++) // k - индекс минимального
if (in[j] < in[k]) k=j; // в диапазоне i..n-1
int c=in[k]; in[k] = in[i]; in[i] = c; // Три стакана для очередного
}} // и минимального
В сортировке выбором контекст выбора минимального элемента обычно заметен «невооруженным глазом». Но в следующем варианте он совмещен с процессом обмена, и потому не виден: минимальный элемент сразу же перемещается на очередную позицию.
//------------------------------------------------------46-06.cpp
//---- «Законспирированная» сортировка выбором
void sort(int in [], int n) {
for (int i = 0; i < n - 1; i++) // Для очередного i
for (int j = i + 1, k = i; j < n; j++) // Для всех оставшихся
if ( in [j] < in [i]) { // в диапазоне i..n-1
int c = in [i]; in [i] = in [j]; in [j] = c; // сразу же менять с очередным
}
} // Выбор совмещен с обменомСортировка вставками. Основная идея алгоритма: имеется упорядоченная часть, в которую очередной элемент помещается так, что упорядоченность сохраняется (включение с сохранением порядка). Технические детали: можно проводить линейный поиск от начала упорядоченной части до первого большего, чем включаемый, использовать двоичный поиск места в упорядоченной части. Сама процедура вставки включает в себя перемещение элементов массива. В следующем примере последовательность действий по вставке очередного элемента в упорядоченную часть «разложена по полочкам» в виде последовательности четырех действий, связанных переменными (извлечение, поиск места, сдвиг, вставка).
//------------------------------------------------------46-07.cpp
//---- Простая вставка
void sort(int in [], int n) {
for (int i = 1; i < n; i++) { // Для очередного i
int v = in [i]; // сохранить очередной
for (int k = 0; k < i; k++) // поиск места вставки
if ( in [k] > v) break; // перед первым, большим v
for (int j = i - 1; j >= k; j--) // cдвиг на 1 вправо
in [j + 1] = in [j]; // от очередного до найденного
in [k] = v; // вставка очередного на место
}
} // первого, большего негоВ сортировке выбором нет характерных программных контекстов, «ответственных» за вставку: характер программы определяется циклом поиска места вставки, который корректно работает только на упорядоченных данных. Таким образом, получается замкнутый круг для логического анализа, разрываемый только доказательством, основанным на методе математической индукции: вставка на i-ом шаге выполняется корректно в упорядоченных данных, подготовленных аналогичным i-1-ым шагом и т.д до 0.
Вставка погружением. Очередной элемент «погружается» путем ряда обменов с предыдущим до требуемой позиции в уже упорядоченную часть массива, пока «не достигнет дна», либо пока не встретит элемент, меньший себя. Наличие контекста «трех стаканов» делает его подозрительно похожим на обменную сортировку, но это не так.
//------------------------------------------------------46-08.cpp
//----- Вставка погружением, подозрительно похожая на обмен
void sort(int in [], int n) {
for (int i = 1; i < n; i++) // Пока не достигли " дна" или меньшего себя
for (int k = i; k != 0 && in [k] < in [k - 1]; k--) {
int c = in [k]; in [k] = in [k - 1]; in [k - 1] = c;
}
}Небольшое техническое замечание. Сортировка начинается с i=1. Это соответствует погружению второго элемента в упорядоченную последовательность единичной длины, что порождает схоластический вопрос: является ли последовательность из одного элемента упорядоченной или нет. Можно смело сказать: является.
Сортировка Шелла. Существенными в сортировках вставками (или обмена) являются затраты на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить погружение с большим шагом, сразу определяя элемент «по месту», а затем делать точную «подгонку». Так поступает сортировка Шелла: исходный массив разбивается на m частей, в каждую из которых попадают элементы с шагом m, начиная от 0,1,...,m-1 соответственно, то есть
0 , m , 2m , 3m ,...
1 , m+1, 2m+1, 3m+1,...
2 , m+2, 2m+2, 3m+2,...Каждая часть сортируется отдельно с использованием алгоритма вставок или обмена. Затем выбирается меньший шаг, и алгоритм повторяется. Шаг можно выбрать равным степени 2, например 64,32,16,8,4,2,1. Тогда на каждом следующем шаге происходит объединение каждых двух уже упорядоченных групп в одну.
Сортировка Шелла требует четырех вложенных циклов: по шагу сортировки (по уменьшающимся степеням 2 – m=64,32,16…), по группам – (по индексу первого элемента в диапазоне k=0…s-1), а затем два цикла обычной сортировки погружением для элементов группы, начинающейся с k с шагом m. Для двух последних циклов нужно взять базовый алгоритм, заменив шаг 1 на m и поменяв границы сортировки.
//-----------------------------------------------------------------46-09.cpp
//------ Сортировка Шелла с шагом по степеням 2 (погружение)
void shell(int A[], int n) {
for (int m = 1; m < n; m *= 2); // Определение последней степени 2
for (m /= 2; m != 0; m /= 2) // Цикл с переменным шагом m=32,16,8..1
for (int k = 0; k < m; k++) // Цикл по группам k=0..m-1
for (int i = k + m; i < n; i += m) // Погружение с шагом с в группе k
for (int j = i; j >= m && A[j] < A[j - m]; j -= m) {
int cc = A[j];
A[j] = A[j - m];
A[j - m] = cc;
}
}Предыдущий пример демонстрирует «правильный» подход, основанный на постановке задачи: каждая группа сортируется отдельно и для их перебора используется отдельный цикл (с переменной k). На самом деле его можно объединить со следующим, производя погружение сразу по всем группам в одном цикле. Кроме того, последовательность шагов погружения можно выбрать другой, тогда при переходе к следующему шагу группы будут перемешиваться между собой. Например, при формуле шага hi+1=3hi+1 (1,4,13,40,121…) трудоемкость сортировки оценивается как O(N3/2).
//------------------------------------------------------------------46-10.cpp
// Сортировка Шелла. Формула шага h=3h+1
// Погружение с уменьшающимся шагом
void sort(int A[], int n) {
int i, j, h;
for (h = 1; h < n / 9; h = h * 3 + 1); // Определить максимальный шаг
for (; h > 0; h = h / 3) // Одновременно просматриваются все группы
for (i = h; i < n; i++) // Погружение с шагом h
for (j = i; j >= h && A[j] < A[j - h]; j -= h)
{
int c = A[j];
A[j] = A[j - h];
A[j - h] = c;
}
}Обменные сортировки
Обменная сортировка представляет собой самое прямолинейное решение проблемы: если в упорядоченной последовательности все пары соседних элементов упорядочены, то нужно достаточно долго переставлять «неправильные» пары, пока порядок не установится. Как мы уже знаем, для этого достаточно двойного цикла. Первая оптимизация состоит в том, что сортировку можно прекратить, если при просмотре всех пар от начала да конца перестановок не будет.
//-----------------------------------------------------------46-11.cpp
//------Обменная сортировка "пузырьком"
void sort(int A[], int n) {
int i, found; // Количество обменов
do { // Повторять просмотр...
found = 0;
for (i = 0; i < n - 1; i++)
if (A[i] > A[i + 1]) { // Сравнить соседей
int cc = A[i];
A[i] = A[i + 1];
A[i + 1] = cc;
found++; // Переставить соседей
}
} while (found != 0);
} //...пока есть перестановкиОбменные сортировки имеют ряд особенностей. Прежде всего, они чувствительны к степени исходной упорядоченности массива. Полностью упорядоченный массив будет просмотрен один раз, в то время как выбор или вставка будут «изображать бурную деятельность». Кроме того, имеется несколько свойств, на котором основана их оптимизация. Они непосредственно не наблюдаемы в тексте программы, ему не соответствуют никакие программные контексты и они выводятся только «историческим» анализом программы (см. также 2.6).
Эффект «пузырька» состоит в том, что в последовательности сравнений и обменов пар наибольший элемент захватывается и «всплывает» до тех пор, пока не встретит большего себя. Этот элемент становится новым пузырьком и т.д.. Другой эффект, который можно увидеть только непосредственным наблюдением: от места последней перестановки будет находиться упорядоченная часть.
Исходя из установленного свойства, просмотр имеет смысл делать не до конца массива, а до последней перестановки, выполненной на предыдущем просмотре. Для этой цели в программе обменной сортировки необходимо запоминать индекс переставляемой пары, который по завершении внутреннего цикла просмотра и будет индексом последней перестановки. Кроме того, необходима переменная – граница упорядоченной части, которая должна при переходе к следующему шагу получать значение пресловутого индекса последней перестановки. Условие окончания – граница сместится к началу массива.
//---------------------------------------------------------46-12.cpp
//------------ Однонаправленная Шейкер-сортировка
void sort(int A[], int n) {
int i, b, b1; // b граница отсортированной части
for (b = n - 1; b != 0; b = b1) { // Пока граница не сместится к правому краю
b1 = 0; // b1 место последней перестановки
for (i = 0; i < b; i++) // Просмотр массива
if (A[i] > A[i + 1]) { // Перестановка с запоминанием места
int cc = A[i];
A[i] = A[i + 1];
A[i + 1] = cc;
b1 = i;
}
}
}Если же просмотр делать попеременно в двух направлениях и фиксировать нижнюю и верхнюю границы неупорядоченной части, то получим шейкер – сортировку.
//------------------------------------------------------------------46-13.cpp
//-------------- Шейкер - сортировка
void shake(int A[], int n) {
int z = 1, a = 0, b = n - 1, i, last = 0; // a,b - границы, z - направление (шаг)
for (i = 0; a < b;) { // цикл – пока границы не сойдутся
if (A[i] > A[i + 1]) { // обмен с запоминанием места
int c = A[i];
A[i] = A[i + 1];
A[i + 1] = c;
last = i;
}
i += z; // шаг в текущем направлении
if (i == b || i < a) { // достинута граница ???
if (z > 0) i = b = last; // место перестановки - новая
else i = a = last + 1; // граница слева или справа
z = -z; // направление противоположное
}
}
}Попеременное движение в двух направлениях удается сделать введением переменной z –шага, принимающей значения +1/-1. Сама же сортировка программа содержит единственный цикл, который выполняет сравнение очередной пары, переход к следующей и контроль границ, пока границы не сойдутся.
Сортировки распределением
Идея распределения состоит в том, чтобы «разбрасывать» элементы, сообразуясь с их собственными свойствами, либо со свойствами по отношению к другим. Сама идея разбрасывания требует наличия дополнительной памяти, за счет чего можно принципиально снизить трудоемкость. Соответствующие примеры будут рассмотрены позднее в 7.7. Здесь же приведем сортировку подсчетом. Идея алгоритма: количество элементов, меньше текущего, определяет его позицию (индекс) в выходном массиве. Наличие переменной-счетчика и использование его как индекса в выходном массиве являются хорошо заметными программными контекстами. Трудоемкость алгоритма при любых данных Tcp=N2.
//---------------------------------------------------------46-14.cpp
//--------- Сортировка подсчетом
void sort(int in [], int n) {
int i, j, cnt;
int * out = new int[n]; // выходной массив
for (i = 0; i < n; i++) {
for (cnt = 0, j = 0; j < n; j++) // для in[i] подсчет
if ( in [j] < in [i]) cnt++; // меньших его
else // а также равных ему
if ( in [j] == in [i] && j > i) cnt++; // и стоящих слева
out[cnt] = in [i]; // место в выходном
} // определяется счетчиком
for (i = 0; i < n; i++) in [i] = out[i];
delete[] out;
}Ситуация, требующая отдельного рассмотрения – наличие одинаковых элементов (допустим, m). Они будут иметь одинаковые счетчики и, следовательно, попадут в одну и ту же ячейку. Последующие же m-1 элементов окажутся незаполненными. Для исправления ошибки одинаковым элементам нужно придать разный «вес» в зависимости от их взаимного положения. Поэтому элемент считает равные ему элементы, стоящие слева, «меньшими себя».
Сортировки разделением/слиянием Как уже отмечалось, сортировки этого типа используются повторяющийся процесс разделения исходной последовательности на части с последующим их соединением обратно. При этом на одном этапе происходит изменение порядка следования элементов, а другой является чисто формальным. Сами процессы разделения и слияния рассмотрены были в 2.4 как примеры с независимыми перемещениями в массиве.
Сортировки рекурсивным разделением. Сортировки разделяют массив на две части относительно некоторого значения, называемого медианой. Медианой может быть выбрано любое «среднее» значение, например, среднее арифметическое. Сами части не упорядочены, но обладают таким свойством, что элементы в левой части меньше медианы, а элементы правой - больше. Благодаря такому свойству эти части можно сортировать независимо. Для этого нужно вызвать ту же самую функцию сортировки, но уже не по отношению к массиву, а к его частям. Функции, вызывающие сами себя, называются рекурсивными (см. 7.1). Рекурсивный вызов продолжается до тех пор, пока очередная часть массива не станет содержать единственный элемент. Так будет выглядеть «заготовка» сортировки разделением, использующая простейший способ реализации разделения, приведенный в 2.4.
//----------------------------------------------------------------------------------------
void sort(int in [], int a, int b) {
if (a >= b) return; // осталось не более 1 элемента - выход
int i, j, k, n1 = b - a + 1; // размерность интервала
int * out = new tmp[b - a + 1]; // временный массив для разделения
double s;... // вычислить медиану, например (min+max)/2
for (i = a, j = 0, k = n1 - 1; i <= b; i++) // цикл разделения из 2.4 с учетом
... // начала интервала – a
If(j != 0) { // если все элементы одинаковые -
sort(tmp, 0, k); // разделения не будет
sort(tmp, j, n - 1);
}
for (i = a, j = 0; i <= b; i++, j++) in [i] = tmp[j]; // вернуть отсортированные данные
delete[] tmp;
}Сортировки слиянием использует слияние упорядоченных последовательностей. Разделение исходной последовательности на части носит формальный характер. Рекурсивное разделение рассматривается в 7.2. Простое однократное слияние является прекрасной иллюстрацией, как можно достигнуть более высокой эффективности только за счет выполнения любой работы по частям с последующим объединением результатов. Исходный массив разбивается на n частей, каждая из них сортируется независимо, а затем отсортированные части объединяются слиянием. Алгоритм слияния использует стандартные контексты: выбирается строка, в которой первый элемент является минимальным (минимальный из очередных), который «сливается» в выходную последовательность. Исключение его производится путем сдвига содержимого строки к началу, причем в конец добавляется «очень большое число», играющее роль «затычки» при окончании этой последовательности. Двумерный массив произвольной размерности реализован с использованием динамического массива указателей (см.6.3), который при работе даже синтаксически выглядит как обычный. Естественно, что при произвольной размерности входного массива, последняя строка двумерного будет неполной.
//------------------------------------------------------------------------46-15.cpp
//------- Простое однократное слияние
void sort(int a[], int n); // любая сортировка одномерного массива
void big_sort(int A[], int N) {
int max = A[0], i, j, n = sqrt(N) + 1;
int ** B = new int * [n];
for (i = 0; i < n; i++) B[i] = new int[n];
for (i = 0; i < N; i++) {
B[i / n][i % n] = A[i];
if (A[i] > max) max = A[i]; // Распределение
}
for (j = n * n - N; j < n; j++) // Заполнение "хвоста" последнего
B[n - 1][j] = max + 1;
for (i = 0; i < n; i++) sort(B[i], n); // Сортировка частей
for (i = 0; i < N; i++) { // Слияние
for (int k = 0, j = 0; j < n; j++) // Индекс строки с минимальным
if (B[j][0] < B[k][0]) k = j; // начальным B[k][0]
A[i] = B[k][0]; // Перенос элемента
for (j = 1; j < n; j++)
B[k][j - 1] = B[k][j]; // Сдвиг сливаемой строки
B[k][n - 1] = max + 1; // Запись ограничителя
}
for (i = 0; i < n; i++) delete[] B[i];
delete[] B;
}При оценке трудоемкости будем использовать «принцип квадрата» - из всех прямоугольников с заданным периметром максимальная площадь будет у квадрата. Не утруждая себя доказательством (а его достаточно просто провести по аналогии), будем считать, что линейный массив разбивается на n=√N частей размерности n. Предположим, что мы используем самую неэффективную сортировку частей с оценкой трудоемкости O(n2), например, сортировку выбором с трудоемкостью сравнений Tср=n2/2. Тогда независимая сортировка частей даст нам nTср = n3/2 = N3/2/2. При слиянии мы переносим N элементов, для каждого из которых используется выбор минимального из не более чем n элементов, т.е. оценка трудоемкости слияния Tср(N) =nN = N3/2. В целом получим Tср(N) = 1.5N3/2 = O(N3/2).Т.е. только за счет «организационных мер» удалось уменьшить трудоемкость с исходной N2/2 до 1.5N3/2, т.е. в √N/3 раза.
Циклическое слияние. Все сортировки так или иначе меняют элементы местами. При этом позиции элементов, с которыми работает программа, меняются нерегулярным (произвольным) образом. Например, в сортировке выбором позиция минимального элемента «случайна». Даже в тех случаях, когда индексы движутся по массиву линейно, обмен также происходит между произвольными парами. Это называется произвольным доступом. Циклическое слияние оригинально уже тем, что использует только последовательный просмотр и перемещение элементов, что внешне воспринимается как «сортировки без сортировки». Сортировка базируется на том факте, что при слиянии двух упорядоченных последовательностей длиной s получается последовательность удвоенной длины. Поэтому основная идея состоит в том, что две последовательности сливаются, но не просто, а группами или слоями толщиной s элементов. В результате получается последовательность с группами по 2s элементов.
Первоначально s=1, что соответствует исходной последовательности. Она, само собой, не упорядочена, то в то же время каждый ее отдельный элемент «упорядочен сам в себе». Главный цикл включает в себя разделение последовательности на две части и их обратное слияние в одну. На первом слиянии в последовательности имеются упорядоченные группы длиной s=1, на втором – s=2, и далее s=4,8,16…2m. Процесс слияния происходит точно так же, как это было описано выше, но он не может выйти за пределы очередной группы, пока обе сливаемые группы не закончились. Это значит, что переход к следующей паре осуществляется «скачком».
//--------------------------------------------------------------------------------46-16.cpp
//------ Циклическое двухпутевое слияние
void sort(int A[], int n) {
int i, i1, i2, s, k;
for (s = 1; 1; s *= 2) { // Размер группы кратен степени 2
int nn = n / s; // Количество групп по s элементов
if (n % s != 0) nn++; // Остаток – есть неполная группа
int n1 = nn / 2 * s; // Деление ближе к середине,
int n2 = n - n1; // но кратно размеру группы
if (n1 <= 0 || n2 <= 0) return; // Часть больше целого - выход
int * B1 = new int[n1], * B2 = new int[n2];
for (i = 0; i < n1; i++) B1[i] = A[i]; // Разделение на части
for (i = 0; i < n2; i++) B2[i] = A[i + n1];
i1 = i2 = 0;
for (i = 0, k = 0; i < n; i++) { // Слияние с переходом «скачком»
if (i1 == s && i2 == s) // при достижении границ обеих
k += s, i1 = 0, i2 = 0; // групп
if (i1 == s || k + i1 == n1) A[i] = B2[k + i2++]; // Достигла границы группы или
else // массива
if (i2 == s || k + i2 == n2) A[i] = B1[k + i1++];
else // Если нет – минимальный из пары
if (B1[k + i1] < B2[k + i2]) A[i] = B1[k + i1++];
else A[i] = B2[k + i2++];
}
delete[] B1;
delete[] B2;
}
}А теперь рассмотрим технологические приемы. Здесь важно правильно выбрать «систему координат», используемую при слиянии групп. В выходной последовательности используется индекс i, который «равномерно» движется по массиву. Слияние всех групп происходит в одном цикле, за один шаг которого происходит перенос одного элемента. Движение же по группам «неравномерное», более того, переход к следующему слою осуществляется скачком, когда обе группы в текущем слое уже слиты. Движение по группам разложено на две составляющие: k – общий индекс начала слоя, а i1,i2 – относительные индексы внутри групп. Здесь же отрабатывается «скачок» к следующему слою: при условии, что обе группы закончились (i1==s && i2==s) обнуляются относительные индексы в группах, а k переносится на начало следующего. В процессе слияния отрабатываются четыре возможные ситуации: завершение первой или второй группы и выбор минимального из пары очередных элементов групп – в противном случае.
Главный цикл организован формально: переменная s принимает значения степени 2. В теле цикла сначала производится разделение массива на две части, а затем - их слияние. Дополнительную головную боль создает произвольная размерность входного массива. Во-первых, разделение нужно проводить на две части, кратные размеру группы (т.е.по ее границе), а во вторых, одна из групп может оказаться неполной. Это решается косметическими поправками: определяется количество групп с учетом неполной, затем делится пополам и умножается на размер группы – получаем размер первой части(n1). В процессе слияния появляются дополнительные условия к проверкам границ групп – проверка границ сливаемых частей.
Оценка трудоемкости производится достаточно просто. Если принять размерность массива равной N=2k, то главный цикл будет выполняться k=log2(N) раз. За этот шаг N элементов переносятся при разделении и N элементов – обратно при слиянии, прочем количество перемещений не зависит от значений (нечувствительность к данным). Tmove=2N log2(N). Сравнений будет меньше, чем Nlog2(N), т.к. они происходят, когда обе текущие группы не пусты. В целом же имеем Omax(Nlog2(N)) по всем основным операциям.
Лабораторный практикум
Алгоритм сортировки реализовать в виде функции, возвращающей в качестве результата характеристику трудоемкости алгоритма (например, количество сравнений). Для получить трудоемкость для различных значений N=1000,5000,10000. Сравнить с теоретической оценкой.
Модификация сортировки циклическим слиянием. Для разграничения сливаемых групп в последовательности в качестве разделителя добавить «очень большое значение» (
MAXINT). Переход к следующей паре групп производить при обнаружении одновременно двухMAXINT.Модификация простого однократного слияния. Разделить массив на n частей и отсортировать их произвольным методом. Отсортированный массив получить путем однократного слияния упорядоченных частей. Для извлечения очередных элементов из упорядоченных массивов использовать массив из n индексов (по одному на каждый массив).
Модификация сортировки Шелла. Пузырьковая сортировка с шагом M, т.е. просмотр пар 0--M,1--M+1, 2—M+2 и т.д. до тех пор, пока есть перестановки при однократном просмотре, затем уменьшение шага в 2 раза.
Модификация обменной сортировки. M раз повторяется процесс цикл предварительного обмена. Просматривается массив и текущий элемент i обменивается с элементом с индексом j, который определяет конечное местоположение A[i], исходя из предположения о линейном возрастании значений в выходном массиве
j = (A[i]-Amin) *n/ (Amax-Amin).
Обмен происходит, как в обычной сортировке, если пара не находится в порядке возрвастания (с учетом взаимного расположения i,j). Окончательно массив досортировывается обычным пузырьком.
Сортировка c предварительным выбором. Из массива путем однократного просмотра выбирается последовательность подряд расположенных элементов, находящихся в порядке возрастания, переносятся в выходной массив и заменяются во входном на -1. Затем оставшиеся элементы включаются в полученную упорядоченную последовательность методом погружения. Проверить эффективность на массивах, содержащих значения, возрастающие «с большой вероятностью».
Сортировка c предварительным выбором. Из массива путем однократного просмотра выбирается последовательность элементов, находящихся в порядке возрастания и переносится очередную строку двумерного массива с заменой во входном на -1. Этот процессс повторяется, пока в массиве не останется возрастающих последовательностей. После этого в масссиве остается последовательность в порядке убывания, которая также заносится в строку массива «задом наперед». Затем для строк производится однократное слияние. Если строрки в двумерном массиве окончатся раньше, после слияния оставшиеся элементы добавляются в выходной массив при помощи погружения.
Сортировка с предварительным размещением. Выходной массив заполняется значениями -1. Делается попытка разместить каждый элемент входного массива в выходном. Индекс размещения j формируется исходя из предположения о линейном возрастании значений в выходном массиве
j = (A[i]-Amin) *n/ (Amax-Amin).
Если элемент в выходном массиве уже занят, то текущий остается во входном, иначе он переносится в выходной, а во входном заменяется на -1. После чего выходной массив уплотняется (удаляются -1), а оставшиеся элементы входного добавляются в выходной при помощи вставки погружением.
Сортировка «демоном Максвелла» (http://habrahabr.ru/post/161835/): Ёмкость с газом разделена на две половины непроницаемой стенкой. В стенке есть отверстие, которое снабжено специальным устройством, которое назовём демоном Максвелла. Демон устроен так, что через отверстие он из левой части в правую пропускает только быстрые (горячие) молекулы газа, а из правой в левую — медленные (холодные) молекулы. Идея решения: интервал массива делится пополам, справа выбирается максимум, слева – минимум. Затем в промежуточный массив переносятся из левой части: меньшие правого минимума – с левого конца, иначе с правого, из правой части: большие левого максимума - с левого конца, иначе с правого. Получается новая граница (это и есть демон Максвелла для чисел). Данные возвращаются в исходный массив. Процесс повторяется, пока левый максимум не станет меньше правого минимума. Вызывается рекурсия для полученных частей. (аналог рекурсивного разделения).
Сортировка с предварительными обменами. M раз повторяется процесс предварительного обмена. Выбирается случайная позиция i=i0 и из нее выбирается элемент C=A[i]. Затем вычисляется его новое положение, исходя из из предположения о линейном возрастании значений в выходном массиве
j = (C-Amin) *n/ (Amax-Amin).
Если j и i не равны, выбранный элемент С вытесняет A[j] (обмен С и A[j]) и процесс повторяется для i=j. Иначе процесс вытеснения закачивается записью последного вытесненного значения поиндексу i0. Затем массив досортировывается обычным пузырьком.
- Оптимизированный двоичный поиск. В процессе деления выбирается не середина интервала, а значение, вычисленное из предположения о линейном возрастании значений элементов массива в текущем интервале поиска. Точка деления интервала m выбирается, исходя из пропорции, т.е. исходя из предпложения о линейном возрастании значений на интервале:
(m-a) / (b-a) = (val-F(a)) / (F(b)-F(a)).
Сравнить эффективность на равномерно возрастяющих данных и данных вида a1,a2,а3…,b, где b>>a(i), т.е. последнее значение много больше предыдущих.
Вопросы без ответов
Определить класс сортировки, описать сущность алгоритма, выполнить полный анализ программы (смысл переменных, результат исполнения назначение фрагментов, наличие стандартных программных контекстов). Примечание. Все программы взяты из разделов 4.6 или 7.2 или описаны в них, или несколько иначе реализованы.
//-------------------------------------------1
void sort(int A[], int n){
int *B=new int[n];
int i1,i2,j,s,k;
for (s=1;s<n;s*=2){
for(k=0; k<n; k+=2*s){
for(i1=k,i2=k+s,j=k; j<n && j<k+2*s;j++)
if (i2>=n || i2==k+2*s || i1!=k+s && A[i1]<A[i2])
B[j]=A[i1++];
else
B[j]=A[i2++];
}
for (j=0;j<n;j++) A[j]=B[j];
}
delete B;
}
//------------------------------------------------------2
void sort(int in[], int n){
for ( int i=1; i < n; i++) {
int v=in[i];
for (int k=0; k<i; k++)
if(in[k]>v) break;
for(int j=i-1; j>=k; j--)
in[j+1]=in[j];
in[k]=v;
}}
//------------------------------------------------------3
void sort(int in[],int n) {
for ( int i=1; i<n; i++)
for ( int k=i; k !=0 && in[k] < in[k-1]; k--){
int c=in[k]; in[k]=in[k-1]; in[k-1]=c;
}}
//------------------------------------------------------4
void sort(int A[], int n ){
for (int m=1; m<n; m*=2);
for (m/=2; m!=0; m/=2)
for (int k=0; k<m; k++)
for (int i=k+m; i<n; i+=m)
for (int j=i; j>=m && A[j]<A[j-m]; j-=m){
int cc = A[j]; A[j]=A[j-m]; A[j-m]=cc;
}
}
//-------------------------------------------5
void sort(int A[], int n){
int i,j,h;
for (h=1; h<n/9; h=h*3+1);
for (;h>0;h=h/3)
for (i=h;i<n;i++)
for (j=i;j>=h && A[j]<A[j-h];j-=h)
{ int c=A[j]; A[j]=A[j-h]; A[j-h]=c; }
}
//------------------------------------------------------6
void sort(int A[], int n){
int i,found;
do {
found =0;
for (i=0; i<n-1; i++)
if (A[i] > A[i+1]) {
int cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
found++;
}
} while(found !=0); }
//------------------------------------------------------7
void sort(int A[], int n){
int i,b,b1;
for (b=n-1; b!=0; b=b1) {
b1=0;
for (i=0; i<b; i++)
if (A[i] > A[i+1]) {
int cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
b1=i;
}}}
//------------------------------------------------------------------8
void sort(int A[],int n){
int z=1,a=0,b=n-1,i,last=0;
for (i=0;a<b;){
if (A[i]>A[i+1]){
int c=A[i];A[i]=A[i+1];A[i+1]=c;
last=i;
}
i+=z;
if (i==b || i<a) {
if (z>0) i=b=last;
else i=a=last+1;
z=-z;
}}}
//-------------------------------------------------9
void sort(int in[],int n){
int i,j,cnt;
int *out=new int[n];
for (i=0; i<n; i++){
for ( cnt=0,j=0; j<n; j++)
if (in[j] < in[i]) cnt++;
else
if (in[j]==in[i] && j<i) cnt++;
out[cnt]=in[i];
}
for (i=0; i<n; i++) in[i]=out[i];
delete []out;
}
//------------------------------------------------------10
void sort(int a[], int n); // любая сортировка одномерного массива
void big_sort(int A[], int N){
int max=A[0],i,j,n=sqrt(N)+1;
int **B=new int*[n];
for (i=0; i<n; i++) B[i]=new int[n];
for (i=0; i<N; i++) {
B[i/n][i%n]=A[i];
if (A[i]>max) max=A[i];
}
for (j=n*n-N; j<n;j++)
B[n-1][j]=max+1;
for (i=0; i<n; i++) sort(B[i],n);
for (i=0; i<N; i++){
for ( int k=0, j=0; j<n; j++)
if (B[j][0] < B[k][0]) k=j;
A[i] = B[k][0];
for (j=1; j<n; j++)
B[k][j-1]=B[k][j];
B[k][n-1]=max+1;
}
for (i=0; i<n; i++) delete []B[i];
delete []B;
}
//------------------------------------------------------11
void sort(int A[], int n){
int i,i1,i2,s,k;
for (s=1; 1; s*=2){
int nn=n/s;
if (n%s!=0) nn++;
int n1=nn/2*s;
int n2=n-n1;
if (n1<=0 || n2<=0) return;
int *B1=new int[n1],*B2=new int[n2];
for (i=0; i<n1; i++) B1[i]=A[i];
for (i=0; i<n2; i++) B2[i]=A[i+n1];
i1=i2=0;
for (i=0,k=0; i<n; i++){
if (i1==s && i2==s)
k+=s,i1=0,i2=0;
if (i1==s || k+i1==n1) A[i]=B2[k+i2++];
else
if (i2==s || k+i2==n2) A[i]=B1[k+i1++];
else
if (B1[k+i1 ] < B2[k+i2 ]) A[i]=B1[k+i1++];
else A[i]=B2[k+i2++];
}
delete []B1; delete []B2;
}}
//-------------------------------------------12
void sort(int in[], int out[], int n){
int i,j,k,max;
for (max=in[0],i=0;i<n;i++)
if (in[i]>max) max=in[i];
int *cnt=new int[max+1];
for(i=0;i<=max;i++) cnt[i]=0;
for(i=0;i<n;i++) cnt[in[i]]++;
for(j=0,i=0;i<=max;i++)
while(cnt[i]--!=0)
out[j++]=i;
}
//------------------------------------------------------13
void sort(int in[], int n){
for ( int i=0; i < n-1; i++){
for ( int j=i+1, k=i; j<n; j++)
if (in[j] < in[k]) k=j;
int c=in[k]; in[k] = in[i]; in[i] = c;
}}
//------------------------------------------------------14
void sort(int in[], int a, int b){
int i,j,mode;
if (a>=b) return;
for (i=a, j=b, mode=1; i < j; mode >0 ? j-- : i++)
if (in[i] > in[j]){
int c = in[i]; in[i] = in[j]; in[j]=c;
mode = -mode;
}
sort(in,a,i-1); sort(in,i+1,b);}
//-----------------------------------------------------15
void sort(int in[], int a, int b){
int i,j,mode;
double sr=0;
if (a>=b) return;
for (i=a; i<=b; i++) sr+=in[i];
sr=sr/(b-a+1);
for (i=a, j=b; i <= j;)
{
if (in[i]< sr) { i++; continue; }
if (in[j]>=sr) { j--; continue; }
int c = in[i]; in[i] = in[j]; in[j]=c;
i++,j--;
}
if (i==a) return;
sort(in,a,j); sort(in,i,b);}
//--------------------------------------------------------16
for(j=0;n!=0;j++){
for (k=0,i=1; i<n; i++)
if (A[i]<A[k]) k=i;
B[j]=A[k];
for (;k<n-1;k++) A[k]=A[k+1];
n--;
}
//--------------------------------------------------------17
for(j=0,max=A[0];j<n;j++)
if (A[j]>max) max=A[j];
for(j=0;j<n;j++){
for (k=0,i=1; i<n; i++)
if (A[i]<A[k]) k=i;
B[j]=A[k];
A[k]=max+1;
}
//--------------------------------------------------------18
while(n!=0){
for (k=0,i=1; i<n; i++)
if (A[i]<A[k]) k=i;
c=A[k]; A[k]=A[n-1]; A[n-1]=c;
n--;
}