Сортировка Джона фон Неймана
Содержание
Введение
. Процедура слияние
. Сортировка
сиянием
. Восходящая
сортировка слиянием
. Гибридная
сортировка
. Естественная
сортировка
Заключение
Список литературы
Введение
слияние листинг
программирование алгоритм
В данной курсовой работе мы рассмотрим
сортировку Джона фон Неймана.
Тема нашего исследования
актуальна, она является очень важным для изучения в связи с тем, что сортировка
и поиск данных - это наиболее часто встречающиеся практические задачи,
возникающие при создании программного обеспечения. Сортировка слиянием -
вероятно, один из самых простых алгоритмов сортировки (среди
"быстрых" алгоритмов).
Сортировка слиянием -
стабильный алгоритм сортировки. Это означает, что порядок "равных"
элементов не изменяется в результате работы алгоритма. В некоторых задачах это
свойство достаточно важно.
Этот алгоритм был предложен
Джоном фон Нейманом в 1945 году
Везде элементы массивов
нумеруются с нуля.
Целью курсовой работы является
сортировка фон Неймана.
Задача изучить алгоритмы
сортировки слиянием, сортировка слиянием в целом.
Предмет и объект исследования.
Объектом исследования является сортировка фон Неймана. Предметом исследования -
сортировка слиянием, алгоритм сортировки, процедура слияния, восходящая
сортировка слиянием, гибридная сортировка и естественная сортировка.
Методы нашего исследования являются анализ,
синтез, обобщение.
Допустим, у нас есть два
отсортированных массива A и B размерами и
соответственно,
и мы хотим объединить их элементы в один большой отсортированный массив C
размером .
Для этого можно применить процедуру слияния, суть которой заключается в
повторяющемся "отделении" элемента, наименьшего из двух имеющихся в
началах исходных массивов, и присоединении этого элемента к концу
результирующего массива. Элементы мы переносим до тех пор, пока один из
исходных массивов не закончится. После этого оставшийся "хвост"
одного из входных массивов дописывается в конец результирующего массива. Пример
работы процедуры показан на рисунке:
Рис. 1. Пример работы процедуры
слияния
Алгоритм слияния формально
можно записать следующим образом:
(1)
Для обеспечения стабильности
алгоритма сортировки нужно, чтобы в случае равенства элементов тот элемент, что
идёт раньше во входном массиве, попадал в результирующий массив в первую
очередь. Мы увидим далее, что если два элемента попали в разные массивы (A
и B), то тот элемент, что шёл раньше, попадёт в массив A.
Следовательно, в случае равенства элемент из массива A должен иметь
приоритет. Поэтому в алгоритме стои́т
знак вместо
< при сравнении элементов.
Недостатком представленного
алгоритма является необходимость дописывать оставшийся кусок, из-за чего при
дальнейших модификациях алгоритма нам придётся писать много повторяющегося
кода. Чтобы этого избежать, будем использовать чуть менее эффективный, но более
короткий алгоритм, в котором копирование "хвоста" встроено в основной
цикл:
(2)
Очевидно, время работы
процедуры слияния составляет .
Реализация процедуры слияния на
языке программирования C++ представлена в листинге 1.
template<class T> void Merge(T
const *const A, int const nA, T const *const B, int const nB, T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов, // и массива
B, содержащего nB элементов. // Результат записать в массив C. int a(0),
b(0); //Номера текущих элементов в массивах A и B while(
a+b < nA+nB ) //Пока остались элементы в массивах { if(
(b>=nB) || ( (a<nA) && (A[a]<=B[b])
) ) { //Копирую элемент из массива A C[a+b]
= A[a]; ++a; } else { //Копирую элемент из массива
B C[a+b] = B[b]; ++b; } } }
Листинг 1. Компактная (не самая
быстрая) реализация процедуры слияния
. Сортировка слиянием
Процедура слияния требует два
отсортированных массива. Заметив, что массив из одного элемента по определению
является отсортированным, мы можем осуществить сортировку следующим образом:
1. разбить имеющиеся
элементы массива на пары и осуществить слияние элементов каждой пары, получив
отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для
которого не нашлось пары);
2. разбить имеющиеся
отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары;
. если число
отсортированных цепочек больше единицы, перейти к шагу 2.
Проще всего формализовать этот
алгоритм рекурсивным способом (в следующем разделе мы реализуем этот алгоритм
итерационным способом). Функция сортирует участок
массива от элемента с номером a до элемента с номером b:
(3)
Поскольку функция сортирует
лишь часть массива, то при слиянии двух фрагментов ей не остаётся ничего, кроме
как выделять временный буфер для результата слияния, а затем копировать данные
обратно:
Листинг 2. Реализация
сортировки слиянием
Время работы сортировки
слиянием составляет . Пример работы
процедуры показан на рисунке:
Рис. 2. Пример работы
рекурсивного алгоритма сортировки слиянием
. Восходящая сортировка
слиянием
Программа, представленная в
листинге 2, имеет серьёзные недостатки: она выделяет и освобождает много
буферов памяти, и делает копирование результатов слияния в исходный массив
вместо того, чтобы вернуть новый массив в качестве результата (она не может
вернуть новый массив в качестве результата, т.к. на входе получает зачастую
лишь часть большого массива).
Чтобы избавиться от этих
недостатков, откажемся от рекурсивной реализации, и сделаем сортировку
следующим образом:
· выделим временный
буфер памяти размером с исходный массив;
· выполним попарное
слияние элементов, записывая результат во временный массив;
· поменяем местами
указатели на временный массив и на исходный массив;
· выполним попарное
слияние фрагментов длиной 2;
· аналогично
продолжаем до тех пор, пока не останется один кусок;
· в конце работы
алгоритма удаляем временный массив.
Такой алгоритм называется
восходящей сортировкой слиянием. Реализация его на языке программирования C++
приведена в листинге 3.
template<class
T> void
MergeSortIterative(T
*&A, int
const n)
{ //Отсортировать массив A,
содержащий n элементов. // При
работе указатель на A, возможно,
меняется. // (Функция получает ссылку на указатель на A)
T *B(
new T[n]
); //Временный буфер памяти for(int
size(1);
size<n;
size*=2) {
//Перебираем все размеры кусочков для слияния: 1,2,4,8... int
start(0);
//Начало первого кусочка пары for(;
(start+size)<n;
start+=size*2)
{ //Перебираем все пары кусочков, и выполняем попарное // слияние.
(start+size)<n означает, что начало // следующего кусочка лежит внутри
массива Merge(A+start , size, A+start+size, min(size,n-start-size),
B+start ); } //Если последний кусочек остался без пары, просто
копи- // руем его из A в B: for(; start<n; ++start) B[start]=A[start];
T *temp(B); B=A; A=temp; //Меняем местами указатели }
delete[n] B; //Удаляем временный буфер }
Листинг 3. Реализация
восходящей сортировки слиянием
К сожалению, в этот алгоритм не
так просто вписать оптимизацию для случая слияния двух элементов (если нужно,
можно вписать эту оптимизацию в процедуру Merge).
Пример работы программы
листинга 3 показан на рисунке:
Рис. 3. Пример работы
восходящего алгоритма сортировки слиянием
template<class T> void
MergeSortIter2(T *const A, int const n) { //Отсортировать
массив
A, содержащий
n элементов.
T *B( A ); //Буфер
памяти
№1 T *C( new T[n] ); //Буфер
памяти
№2 for(int size(1); size<n; size*=2) { //Перебираем
все
размеры
кусочков
для
слияния:
1,2,4,8... int start(0); //Начало
первого
кусочка
пары
for(; (start+size)<n; start+=size*2) { //Перебираем
все
пары
кусочков,
и
выполняем
попарное
// слияние.
(start+size)<n означает,
что
начало
// следующего
кусочка
лежит
внутри
массива
Merge(B+start , size, B+start+size, min(size,n-start-size),
C+start ); } //Если
последний
кусочек
остался
без
пары,
просто
копи-
// руем
его
из
B в
C: for(; start<n; ++start) C[start]=B[start];
T *temp(B); B=C; C=temp; //Меняем
местами
указатели
} //В
данный
момент
результат
работы
находится
в
массиве
B. if( C == A ) { // Если
массив
C является
массивом
A, то
нужно
// скопировать
результат
работы
из
B в
A. for(int i(0); i<n; ++i) A[i]=B[i];
delete[n] B; //Удаляем
временный
буфер
} else { delete[n]
C; //Удаляем временный
буфер
} }
Листинг 4. Реализация
восходящей сортировки слиянием с сохранением результата работы в исходном
массиве
. Гибридная сортировка
Анализ быстродействия алгоритма
наталкивает нас на мысль объединить преимущества алгоритмов пирамидальной
сортировки и сортировки слиянием. К счастью, сделать это очень просто: нужно
разбить массив сразу на большие кусочки (например, размером 512 элементов), и
применить к ним алгоритм пирамидальной сортировки. Полученные отсортированные
кусочки затем можно "досортировать" слиянием. Используя функции из лекции
5, требуемые изменения в алгоритме минимальны (за основу взята функция из
листинга 3):
template<class
T> void
HybridSort(T
*&A, int
const n)
{ //Отсортировать массив A,
содержащий n элементов. // При
работе указатель на A, возможно,
меняется. // (Функция получает ссылку на указатель на A)
//Размер кусочка для сортировки пирамидой: // (нужно подбирать для
максимального ускорения) int
const tileSize(
4096 ); for(int
start(0);
start<n;
start+=tileSize)
HeapSort(A+start,
min(tileSize,n-start)
); if(
n <= tileSize
)
return; //Больше
сортировать не нужно T
*B(
new T[n]
); //Временный буфер памяти for(int
size(tileSize);
size<n;
size*=2) {
//Перебираем размеры кусочков для слияния, // начиная с tileSize
элементов int
start(0);
//Начало первого кусочка пары for(;
(start+size)<n;
start+=size*2)
{ //Перебираем все пары кусочков, и выполняем попарное // слияние.
(start+size)<n означает, что начало // следующего кусочка лежит внутри
массива Merge(A+start , size, A+start+size, min(size,n-start-size),
B+start ); } //Если последний кусочек остался без пары, просто
копи- // руем его из A в B: for(; start<n; ++start) B[start]=A[start];
T *temp(B); B=A; A=temp; //Меняем местами указатели }
delete[n] B; //Удаляем временный буфер }
Листинг 5. Реализация гибридной
сортировки
. Естественная сортировка
До сих пор мы рассматривали
алгоритмы сортировки, которые никак не учитывают то, что данные (или их часть)
могут быть уже отсортированы. Для алгоритма сортировки слиянием есть очень
простая и эффективная модификация, которая называется "естественная
сортировка" ("Natural Sort"). Суть её в том, что нужно образовывать
цепочки, и производить их слияние не в заранее определённом и фиксированном
порядке, а анализировать имеющиеся в массиве данные. Алгоритм следующий:
1. разбить массив на
цепочки уже отсортированных элементов (в худшем случае, когда элементы в
массиве идут по убыванию, все цепочки будут состоять из одного элемента);
2. произвести слияние
цепочек методом сдваивания.
Пример работы этого алгоритма
показан на рисунке:
Рис. 7. Пример работы
естественного алгоритма сортировки слиянием
В отличие от ранее
рассмотренных вариантов алгоритма слияния, естественная сортировка справилась с
задачей за 3, а не за 4 итерации.
Обратите внимание, что во время
работы алгоритма не могут образоваться новые отсортированные цепочки кроме получившихся
в результате слияний, поэтому поиск отсортированных цепочек должен проводиться
только на первом этапе. Но как хранить найденные цепочки? Выделять для них
память - очень неэффективно. Самый простой способ - вообще их не хранить, а
искать каждый раз заново. Это неэффективно, зато просто:
<class T> void NaturalSort(T
*&A, int const n) { //Отсортировать массив A, содержащий n
элементов. // При работе указатель на A, возможно, меняется. // (Функция
получает ссылку на указатель на A) T *B( new T[n] );
//Временный буфер памяти while(true) //Выполняем слияния, пока не
останется один { // отсортированный участок. Выход из цикла // находится
дальше int start1 ,end1 ; //Первый отсортированный участок int start2(-1),end2(-1);
//Второй отсортированный участок while(true) { //Цикл по
всем парам отсортированных участков в массиве //Начало первого участка для
слияния находится после // конца второго участка предыдущей пары: start1 =
end2+1; end1 = start1; //Двигаемся вправо до нарушения сортировки: while(
(end1<n-1) && (A[end1]<=A[end1+1])
) ++end1; //Первый участок пары простирается до конца массива: if(
end1 == n-1 ) break; //Начало второго участка для слияния находится
после // конца первого участка текущей пары: start2 = end1+1, end2 = start2;
//Двигаемся вправо до нарушения сортировки: while( (end2<n-1)
&& (A[end2]<=A[end2+1]) )
++end2; //Выполняем слияние двух отсортированных участков Merge(A+start1,
end1-start1+1, A+start2, end2-start2+1, B+start1 ); //Второй участок
пары простирается до конца массива: if( end2 == n-1 ) break; }
//Данные полностью отсортированы и находятся в массиве A: if( (start1==0)
&& (end1==n-1) ) break; //Если последний кусочек
остался без пары, просто копи- // руем его из A в B: if( end1 == n-1 )
{ for(; start1<n; ++start1) B[start1]=A[start1];
} T *temp(B); B=A; A=temp; //Меняем местами указатели }
delete[n] B; //Удаляем временный буфер }
Листинг 8. Исходный код
алгоритма естественной сортировки слиянием
Несмотря на то, что
представленная реализация на каждой итерации примерно 25% времени проводит в
поиске отсортированных фрагментов для слияния (хотя этот поиск достаточно
произвести только в начале), она показывает неплохие результаты для случайного
набора чисел:
Рис. 8. Отношение времени
сортировки к . Красный цвет -
естественная сортировка, серый цвет - восходящая сортировка слиянием
Заключение
В данной работе была изучена подробно сортировка
слиянием, алгоритм сортировки, процедура слияния, восходящая сортировка
слиянием, гибридная сортировка и естественная сортировка.
Особенностью этого алгоритма является то, что он
работает с элементами массива преимущественно последовательно, благодаря чему
именно этот алгоритм используется при сортировке в системах с различными
аппаратными ограничениями (например, при сортировке данных на жёстком диске,
или даже на магнитной ленте). Кроме того, сортировка слиянием - чуть ли не
единственный алгоритм, который может быть эффективно использован для сортировки
таких структур данных, как связанные списки. Последовательная работа с
элементами массива значительно увеличивает скорость сортировки в системах с
кэшированием.