Московский авиационный институт
(НИУ)
Лабораторная работа №13
"Методы сортировки II"
Вариант № 7
Группа: 7О-102С
Выполнила:
Проверил:
Москва 2016
Цель работы: знакомство с пирамидальным методом сортировки, быстрой сортировкой и сортировкой методом слияния.
сапарбаевакатя, 1 53 67 39 76 0 30 50
Рекурсивные алгоритмы (примеры).Рекурсия – фундаментальное понятие в математике и компьютерных науках. В языках программирования рекурсивной программой называется программа, которая обращается сама к себе (подобно тому, как в математике рекурсивная функция определяется через понятия самой этой функции). Рекурсивная программа не может вызывать себя до бесконечности, следовательно, вторая важная особенность рекурсивной программы – наличие условия завершения, позволяющее программе прекратить вызывать себя.
Рекурсивный алгоритм всегда разбивает задачу на части, которые по своей структуре являются такими же как исходная задача, но более простыми. Для решения подзадач функция вызывается рекурсивно, а их результаты каким-либо образом объединяются. Разделение задачи происходит лишь тогда, когда ее не удается решить сразу (она является слишком сложной).
Например, задачу обработки массива нередко можно свести к обработке его частей. Деление на части выполняется до тех пор, пока они не станут элементарными, т. е. достаточно простыми чтобы получить результат без дальнейшего упрощения.
- Рисование дерева
Если каждую линию считать узлом, то данное изображение вполне удовлетворяет определению дерева. Рекурсивная процедура, очевидно должна рисовать одну линию (ствол до первого разветвления), а затем вызывать сама себя для рисования двух поддеревьев. Поддеревья отличаются от содержащего их дерева координатами начальной точки, углом поворота, длиной ствола и количеством содержащихся в них разветвлений (на одно меньше). Все эти отличия следует сделать параметрами рекурсивной процедуры.
Деревья используются как для упрощения понимания и анализа рекурсивных программ, так и в качестве явных структур данных.
Рекурсивный алгоритм может быть записан в виде рекурсивной функции. Классическими примерами рекурсивных функций являются функции для вычисления факториала, чисел Фибоначчи и наибольшего общего делителя с помощью алгоритма Эвклида.
- Ханойские башни
Имеется три стержня A, B, C. На стержне А надето N колец, причем кольцо меньшего диаметра должно располагаться над кольцом большего диаметра. Требуется переместить N колец с А на С, используя В как промежуточный стержень. При перемещении колец кольцо меньшего диаметра можно класть поверх кольца большего диаметра, но не наоборот.
Данную головоломку в конце XIX в. предложил французский математик Эдуард Люка, где использовалось 7-8 дисков.
Простые методы сортировки вроде метода выбора или метода пузырька сортируют массив из n элементов за O(n2) операций. Однако с помощью принципа «разделяй и властвуй» удается построить более быстрые, работающие за O(n log2 n) алгоритмы. Суть этого принципа в том, что решение получается путем рекурсивного разделения задачи на несколько простые подзадачи того же типа до тех пор, пока они не станут элементарными.
- Быстрая сортировка
Алгоритм быстрой сортировки на каждом шаге выбирает один из элементов (опорный) и относительно него разделяет массив на две части, которые обрабатываются рекурсивно. В одну часть помещаются элементы меньше опорного, а в другую – остальные.
- Сортировка слиянием
В основе алгоритма сортировки слиянием лежит возможность быстрого объединения упорядоченных массивов (или списков) так, чтобы результат оказался упорядоченным. Алгоритм разделяет исходный массив на две части произвольным образом (обычно пополам), рекурсивно сортирует их и объединяет результат. Разделение происходит до тех пор, пока размер массива больше единицы, т. к. пустой массив и массив из одного элемента всегда отсортированы.
На каждом шаге слияния из обоих списков выбирается первый необработанный элемент. Элементы сравниваются, наименьший из них добавляется к результату и помечается как обработанный. Слияние происходит до тех пор, пока один из списков не окажется пуст.
- Пирамидальная сортировка
Aлгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за ?(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает parent/ тонет child по многим путям.
1. Пирамидальная сортировка (описание, две пирамиды, функция).
function m=www(m)
len=uint32(length(m));
head=bitshift(len,-1);
while head>0
parent=head;
while parent<=bitshift(len,-1)
child=2*parent;
if child+1 <= len && m(child)<m(child+1)
child=child+1;
end
if m(child) > m(parent)
tmp=m(child);
m(child)=m(parent);
m(parent)=tmp;
parent=child;
else
break
end
end
head=head-1;
end
tmp=m(1);m(1)=m(len);m(len)=tmp;
len=len-1;
while len>1
parent=1;
while parent <= bitshift(len,-1)
child=2*parent;
if child+1<=len && m(child)<m(child+1)
child=child+1;
end
if m(child)>m(parent)
tmp=m(child);
m(child)=m(parent);
m(parent)=tmp;
parent=child;
else
break
end
end
tmp=m(1);m(1)=m(len);m(len)=tmp;
len=len-1;
end
end
function Z=www(m)
Y = www(m);
i = length(m):-1:1;
Z = Y(i);
end
1. Построение пирамиды
Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим потомкам (таким образом, на вершине дерева всегда находится наибольший элемент).
Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т. е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).
Таким образом, для того, чтобы каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].
2. Сортировка
В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т. е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.
На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.
>> www(m)
ans =0 1 30 39 50 53 67 76
>> www(k)
ans =ааааабвекпрстя
2. Быстрая сортировка (описание, два примера, функция).
1. Выбирается опорный элемент (например, первый или случайный).
2. Реорганизуем массив так, чтобы сначала шли элементы меньшие опорного, потом равные ему, затем большие. Для этого достаточно помнить, сколько было найдено меньших (m1) и больших (m2), чем опорный и ставить очередной элемент на место с индексом m1, а очередной больший на место с индексом n-1-m2.
После выполнения такой операции опорный элемент и равные ему стоят на своем месте, их переставлять больше не придется. Между «меньшей» и «большей» часть массива перестановок также быть не может. То есть эти части можно сортировать независимо друг от друга.
3. Если «меньшая» или «большая» часть состоит из одного элемента, то она уже отсортирована и делать ничего не надо. Иначе сортируем эти части с помощью алгоритма быстрой сортировки (то есть, выполняем для нее шаги 1-3).
function m=vvv(m)
if length(m)<=1
return;
elseif length(m)==2
if m(1)> m(2), tmp= m(1);m(1)=m(2); m(2)=tmp;end
else
less = m(1:end-1)<m(end);
equal = m(1:end)==m(end);
greater = m(1:end-1)>m(end);
m=[ vvv(m(less)),m(equal), vvv(m(greater)) ];
end
>> vvv(m)
ans =0 1 30 39 50 53 67 76
>> vvv(k)
ans =ааааабвекпрстя
3. Анализ времени, затрачиваемого на сортировку числовых массивов шестью методами (простая вставка, простой выбор, "пузырек", пирамидальная, быстрая). Размеры массивов случайных чисел: 1000, 2000, 3000, 4000, 5000, 6000, 7000.
N=1000:1000:7000;
T=zeros(1,length(N));
n=1;
for p=N
m=fix(100*randn(1,p));
tic
ppp(m);
T(1,n)=toc;
tic
qqq(m);
T(2,n)=toc;
tic
ddd(m);
T(3,n)=toc;
tic
www(m);
T(4,n)=toc;
tic
vvv(m);
T(5,n)=toc;
n=n+1;
end
figure('numbertitle','off','name','Сравнение по времени')
plot(N, T(1,:),'or',N, T(2,:),'vm',N, T(3,:),'hy',N, T(4,:),'*b',N, T(5,:),'xk','linewidth',4);
grid on
xlabel('Размер массива');
ylabel('Время, с');
legend('Метод вставки','Метод простого выбора', 'Метод ''Пузырька''','Метод пирамидальный','Метод быстрой сортировки');
Дополнительно:
k=('сапарбаевакатя')
m=([1 53 67 39 76 0 30 50 ])
Вывод: Анализ алгоритмов показывает, что: у пирамидальной сортировки достоинством является не использование дополнительной памяти или очень незначительно, но алгоритм сложен в реализации, неустойчив (по ходу работы массив так "перетряхивается", что исходный порядок элементов изменяется случайным образом), и на почти отсортированных массивах работает столь же долго, как и на хаотических данных. К тому же частичная упорядоченность массива никак не учитывается. Алгоритм «Быстрая сортировка» хотя неустойчив и использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n). А данные о рекурсивных подвызовах каждый раз добавляются в стек и возможны. В принципе, ситуации, когда эти данные переполнят внутренний стек данных сопроцессора, рассчитанный на определённое число уровней рекурсии, является самым эффективным из рассмотренных алгоритмов рекурсии. Известно, что при относительной простоте написания, у всех рекурсивных подпрограмм часто встречается существенный недостаток – неэффективность. Неэффективность рекурсии проявляется в том, что одни и те же вычисления производятся по многу раз. Рекурсивная запись алгоритма, как правило, не дает выигрыша в скорости его работы. Скорее наоборот, так как вызов любой функции связан с сохранением и восстановлением контекста вызывающей функции, что является затратной по времени операцией. Кроме того, для хранения контекста операционной системой резервируется специальная секция памяти, называемая системным стеком. Если цепочка вызовов функций является длинной (иногда говорят о большой глубине рекурсии), то это может привести к переполнению стека. Например, при вычислении факториала числа 25 глубина рекурсии достигает значения 24.
Опыт, полученный, при выполнении этого задания позволит в дальнейшем выбрать подходящий алгоритм для проведения каких-либо расчётов, используя полученные навыки.
