Уханов - лекции

После первого обмена ключей местами увеличим i на единицу и будем продолжать сравнения, увеличивая i, пока не произойдет еще один обмен. Тогда опять будем уменьшать j.

2 3 8 6 4 9 5 7

i j

2 3 8 6 4 9 5 7

i j

2 3 5 6 4 9 8 7

i j

Будем продолжать процесс до тех пор, пока i не станет равно j.

2 3 5 6 4 9 8 7

i j

2 3 4 6 5 9 8 7 i j

2 3 4 5 6 9 8 7

i j

Этот процесс назовем расщеплением. Отметим, что в каждом сравнении этого примера участвует ключ 5. Вообще в каждом сравнении будет участвовать исходный ключ k1. К моменту, когда i станет равно j, исходная запись с ключом k1 займет свою окончательную позицию. Все ключи слева от k1 будут меньше, а справа больше. Ключ 5 называется точкой расщепления или ключом расщепления. Для сортировки левой и правой частей рекомендуется применить тот же метод. Таким образом, налицо рекурсия.

Пример:

Сортировка целых чисел. Процесс расщепления:

//t – сортируемый массив, i, j – расщепляемый участок.

//Функция возвращает индекс в точке расщепления

int Partition (int *t, int i, int j) { int b;

b = 1;

while (i < j) {

if (t [i] > t [j]) { b = !b;

t [i] ↔ t [j];

}

if (b) j --; else i ++;

}

return i;

}

Сортировка:

//t – сортируемый массив, i, j – расщепляемый участок void Hoar (int *t, int i, int j) {

if (! (i < j)) return; k = Partition (t, i, j); Hoar (t, i, k-1); Hoar (t, k+1, j);

}

Обращение к функции:

//t – сортируемый массив, n – размерность массива void qsort (int *t, int n) {

Hoar (t, 0, n-1);

}

Оценим трудоемкость алгоритма.

Простую прикидку числа сравнений можно произвести, если предположить, что на каждой

стадии деление массива происходит точно пополам. При разделении полной таблицы потребуется выполнить N сравнений. При работе с двумя частями разделенной таблицы потребуется 2(N/2) = N сравнений и т.д. Число дроблений таблицы, очевидно, равно log2N. Следовательно, суммарное число сравнений пропорционально N log2 N . В действительности, деление происходит

не пополам, поэтому сравнений будет больше.

Интересно, что применение алгоритма к сортированной последовательности потребует

N(N −1) ~ N2 сравнений, т.к. каждая операция расщепления становится бесполезной. Таким

2

образом, алгоритм предпочитает несортированные таблицы.

Для исправления ситуации Хоаром предложено два способа выбора ключа расщепления:

1)на отрезке (i, j) возьмем медианный ключ k(i+j)/2. Поменяем местами ki и k(i+j)/2 и начнем расщепление;

2)на отрезке (i, j) возьмем случайный ключ km, поменяем местами ki и km и начнем расщепление.

При таких манипуляциях среднее время работы алгоритма будет N log2 N .

Сортировка ненатуральных чисел

//base – базовый адрес начала таблицы

//size – размер записи в таблице

//n – количество записей в таблице

//cmp – указатель на функцию сравнения ключей двух записей

//функция сравнения должна возвращать < 0, если I < II, = 0, если I = II, > 0, если I > II void Sort (void *base, int size, int n, int (*cmp)(void*, void*)) {

int i, j, k; char s;

for (i = 0; i < n-1; i ++) { k = i;

for (j = i + 1; j < n; j ++) {

if ((*cmp)((char*)base + j*size, (char*)base + k*size) < 0) k = j;

}

for (j = 0; j < size; j ++) {

s = *((char*)base + i*size;

*((char*)base + i*size + j = *((char*)base + k*size + j; *((char*)base + k*size + j = s;

}

}

}

Разделяющие сортировки

Основная идея разделяющей сортировки заключается в следующем. Пусть А – исходное множество сортируемых ключей. Допустим нам удалось разбить это множество на попарно непересекающиеся подмножества А0, А1, …, Аm такие, что Аj<Aj+1, т.е. любой ключ из Аj меньше любого ключа из Aj+1. Если это удалось вделать, то подвергнув каждое из подмножеств такому процессу получим сортированную последовательность. К этому классу может быть отнесена сортировка Хоара.

Двоичная поразрядная сортировка

Ключ рассматривается как последовательность битов. Устанавливаем указатели на начало и конец таблицы. Двигаемся слева направо от начала в поисках ключа со старшим битом 1. Двигаемся справа налево от конца в поисках ключа со старшим битом 0. Меняем местами эти ключи. Продолжаем встречное движение по данному принципу до встречи. В результате таблица расщепляется на две части. В левой части все ключи имеют старший бит равный 0, в правой – 1. Таким образом, Aj<Aj+1. Затем эта процедура выполняется для второго бита и полученных подпоследовательностей и т.д.

Пример:

010 101 111 001 011 100

010 101 111 001 011 100

010 011 001 111 101 100

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

Число расщеплений будет равно log2N. Каждый раз будем просматривать N элементов. Таким образом, время сортировки пропорционально N log2 N .

Функция расщепления.

//t – указатель на начало таблицы

//l, r – границы расщепляемого участка

//keylen – длина ключей

//nombit – номер бита, по которому происходит расщепление

//возвращает индекс самого правого ключа с битом nombit равным нулю int BitPart (char *t, int keylen, int l, int r, int nombit) {

lb = GiveBit (lrec, nombit); rb = GiveBit (rrec, nombit); if (!lb && !rb) l ++;

if (!lb && rb) { l ++;

r --;

}

if (lb && !rb) {

l ++; r --;

Change (lrec,rrec);

}

if (lb && rb) r --;

}

if (lb && rb) return r-1; else return r;

}

Функция сортировки.

//выполняет сортировку участка от l до r таблицы t с длинной ключа

//keylen по биту, начиная с nombit

void BSort (char *t, int l, int r, int keylen, int nombit) {

}

Обращение к функции BSort. // n – число ключей

void BitSort (char *t, int keylen, int n) { BSort (t, 0, n-1, keylen, 0);

}

static unsigned char bits [ ] = {128, 64, 32, 16, 8, 4, 2, 1};

// record – указатель на запись, из которой выделяем один бит int GiveBit (char *record, int nombit) {

int NomByte; int BitInByte;

NomByte = nombit / 8; BitInByte = nombit % 8;

return (record [NomByte] & bits [BitInByte]) >> BitInByte;

}

Цифровая поразрядная сортировка по принципу «сначала по младшей цифре»

Возьмем в нулевое множество все ключи с младшим битом 0, в множество с индексом 1, ключи с младшим битом 1 и т.д. Затем выполним подсчет ключей в множествах. Таким образом, получим С – массив счетчиков, в котором С [i] – это число ключей со старшей цифрой i. После подсчета ясно, что все ключи, имеющие младшую цифру 0, должны помещаться, начиная с нулевой позиции, ключи с цифрой 1 – начиная с позиции С [0], с цифрой 2 – с позиции С [0] + C [1] и т.д. Разместим ключи в соответствии с описанным правилом. Таким образом, добились разделения Ai<Ai+1. Далее повторим процесс по следующей цифре и т.д.

Рассмотрим на примере ключей в троичной системе счисления. Дано множество ключей:

102 211 012 020 201 111 121 022

Для троичной системы счисления размерность массива счетчиков будет три. Тогда С0 будет содержать 1 (имеется только один элемент, с 0 в старшем бите – 020), С1 будет содержать 4 (211, 201, 111, 121), и, наконец, С2 содержит 3 (102, 012, 022). Расставим теперь ключи в соответствии с

Снова повторяем процесс расщепления по следующей цифре.

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

Можно брать любую систему счисления. Удобно, если цифра – бит. Поэтому обычно используются либо 16-ричная (один бит – цифра), либо 256-ричная (один байт – цифра).

Функция, выполняющая сортировку. #define NDIG 256

void DigitalSort(char *t, int N, int KeyLen){

//t - сортируемый массив

//N - его длина

//KeyLen - число цифр в сортируемом ключе

//расчет позиций, откуда будут начинаться записи с соответствующими цифрами

Pos[0]=0;

for(j=1; j<NDIG; j++){ Pos[j]=Pos[j-1]+Count[j-1];

}

//расстановка, в соответствии с номером позиции

for(j=0; j<N; j++){ Dig=*(t+j*KeyLen+KeyLen-i-1);

memcpy(b+KeyLen*Pos[Dig]++, t+j*KeyLen, KeyLen);

}

memcpy(t,b,KeyLen*N); // копирование буфера обратно в t и по следующей цифре

}

free(b);

free(Count);

free(Pos);

}

Сортировки слиянием

Слияние означает объединение двух или более упорядоченных таблиц в одну упорядоченную.

Двухпутевое слияние

Пусть имеется две отсортированные последовательности

1 2 4 7

3 5 8 11.

Требуется получить единую сортированную последовательность.

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

12 4 7

3 5 8 11;

1 2 3 4 5 7 8 11.

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

Простейшая форма сортировки слиянием начинает с подмножеств, состоящих их единичных элементов и объединяет их попарно в N/2, если N четно и N/2+1, если N нечетно, сортированных подмножеств, содержащих по два элемента. Затем эти подмножества снова попарно сливаются, их число снова уменьшается вдвое и т.д., пока таблица не будет отсортирована полностью.

Все слияния, выполняемые при переходе из одной области в другую, требуют не более чем N сравнений. Необходимо примерно log2N таких переходов. Следовательно, время работы алгоритма пропорционально N log2 N .

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

Сортировка фон Неймана

Пусть А исходная область памяти. Ключи в этой области имеют частичную упорядоченность. Устанавливаем указатели на начало и конец области.

Выполняем слияние левого и правого участков упорядоченности (а и b). Результат слияния помещаем в начало области B. Двигаясь в достигнутых позициях в А выполняем слияние следующих участков с и d. Результат помещаем в B справа налево от конца. Получаем

Снова перекачиваем в А и приступаем к сортировке. Так до тех пор, пока не будет получен единый участок сортировки.

Напишем функцию слияния двух отрезков.

//а – исходная область – массив целых ключей

//b – область, куда будет помещен результат слияния

//l – указатель на начало левого участка упорядоченности;

//по окончанию работы указатель на начало следующего участка

//r – указатель на начало правого участка упорядоченности;

//по окончанию работы указатель на начало следующего участка

//k – указатель на позицию в b, начиная с которой помещаем в b результат слияния

//step – шаг движения по b (1 или –1).

void Join (int *a, int *b, int *l, int *r, int *k, int step){

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

//и не закончился хотя бы один участок упорядоченности

while (*l < *r && !(bl&&br)) {

if (!bl && (br || f)) {

// если левый участок не окончен, а правый окончен или a [l] < a [r]

//bl || (!br && !f)

//если левый участок окончен или правый не окончен и a [l] > a [r]

}

}

Функция, осуществляющая один проход по множеству ключей.

//а – исходная область – массив целых ключей

//b – область, куда будут помещены результаты слияния

//n – размеры областей

//возвращает число отсортированных отрезков в области b int OnePass (int *a, int *b, int n) {

}

Функция сортировки

//a – сортируемый массив

//n – размерность массива void Neumann (int *a, int n) {

}

Если таблица случайна, то в ней около N/2 упорядоченных участков, так как ситуация, что ki > ki+1 равновероятна ситуации ki < ki+1. При каждом просмотре множества ключей число отрезков упорядоченности сокращается вдвое за счет слияния. Таким образом, число просмотров в среднем равно log2N. При каждом просмотре требуется переписать все N записей в другую область. Следовательно, время сортировки пропорционально N log2 N .

Внешние сортировки

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

Метод пузырька

Исходная таблица располагается в файле на диске.

Разобьем всю внешнюю таблицу на N зон так, чтобы в оперативную память можно было поместить две зоны. Считываем первые две зоны и выполняем внутреннюю сортировку. У получившегося множества нижнюю половину записываем в первую зону. На освободившееся место подкачиваем третью зону, сортируем и нижнюю половину переписываем во вторую зону. На освободившееся место подкачиваем четвертую зону и т.д.

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

Время сортировки пропорционально N2.

Двухпутевое слияние

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

Пусть требуется отсортировать таблицу из 500 записей, а пространство в оперативной памяти есть только под 100 записей. Рассмотрим сортировку на трех файлах.

f1, f2, f3 – используемые файлы.

Будем читать исходный файла по 100 записей за раз. Для прочитанных записей будем выполнять внутреннюю сортировку и результат поочередно дописывать в файлы f1 и f2, пока не исчерпаются входные данные. Эта начальная распределительная фаза процесса сортировки поместит пять отрезков в файлы следующим образом:

f1: записи 1-100, 201-300, 401-500; f2: записи 101-200, 301-400;

f3: пусто.

Таким образом, получили в файлах f1, f2 группы сортированных кусков. Выполняем внешнее двухпутевое слияние файлов f1 и f2 в файл f3. Получаем:

f1: пусто; f2: пусто;

f3: записи 1-200, 201-400, 401-500.

Получили отрезки вдвое более длинные, чем исходные. Поочередно копируем отрезки в файлы f1 и f2. Вновь повторяем процесс слияния. Так до тех пор, пока не получим единственный отрезок в файле.

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

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

Порождение начальных отрезков

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

Имеется память под N записей. Читаем первые N записей, отыскиваем среди них запись с наименьшим ключом и помещаем ее на выход. На ее место подкачивается новая запись из входного файла, причем если ее ключ больше, чем ключ только что выведенной записи, то она будет участвовать в выборе, в противном случае не будет. Снова выбираем запись с наименьшим ключом и т.д. Когда в памяти не останется ни одной записи, которой разрешено участвовать в выборе, порождение отрезка закончено и начинается порождение следующего отрезка.

Пример:

Имеем последовательность

17 12 6 13 18 9 11 4 2 8 26 5 7 19 29 41

и имеем место в оперативной памяти под 4 записи. Читаем первые четыре записи:

Снова выбираем наименьшее 12 и на выход. На его место подкачиваем 9, меньше чем 12, следовательно в выборе не участвует. Отметим этот факт скобками и т.д.

(4)(9) (2) (11)

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

Таким образом, получили три начальных отрезка. Причем длина отрезков больше объема оперативной памяти.

Фибоначчиево слияние

Копирования при слиянии можно устранить полностью, если начать с Fn отрезков в файле f1 и с Fn-1 отрезков в файле f2, где Fn и Fn-1 – последовательные числа Фибоначчи.

Числа Фибоначчи:

F0 = 0;

F1 = 1;

F2 = F1 + F0;

..........

Fn = Fn-1 + Fn-2 + ... + F0. 0 1 1 2 3 5 8 13 21 34 ...

Рассмотрим множество из 34 начальных отрезков. Распределим отрезки по двум файлам f1 и f2 и будем выполнять слияние с использованием файла f3.

Процесс фибоначчиева слияния можно проиллюстрировать таблицей: