Алгоритм быстрой сортировки
Обменная сортировка с разделением – это лучший из универсальных алгоритмов, разработанных к настоящему времени. Относится к группе алгоритмов обменной сортировки (как и пузырьковая сортировка).
Сортируемый массив разбивается на два подмассива, для чего сначала выбирается пограничное значение - компаранд. Все элементы, большие компаранда, переносятся в один массив, а меньшие - в другой. Весь процесс повторяется для каждого подмассива до тех пор, пока массив не будет отсортирован.
Перенос в подмассивы происходит следующим образом:
Существует два индекса i и j, причем сначала i=0, j=N-1.
Сравниваются элементы k[i] и k[j], если обмен не требуется, то j уменьшается на единицу и сравнения повторяются, а j с каждым шагом уменьшается на 1.
После первого обмена i увеличивается на единицу и сравнения повторяются с увеличением i на 1, пока не произойдет следующий обмен, после которого опять начинает убывать j. И так до тех пор, пока не i и j не будут равны друг другу.
Исходный массив подвергается рекурсивному процессу.
Представляет интерес вопрос о выборе компаранда. Существуют варианты:
Случайный выбор - иногда бывает наилучшим;
Выборка небольшого числа элементов из подмассива и использовании в качестве компаранда медианы выборки. Широко распространен и эффективен метод - выборка трех элементов и взятие среднего из них;
Один из экстремумов - наихудьший вариант, хотя алгоритм работает;
Средний элемент каждого из подмассивов.
Пример последнего варианта:
Программа быстрой сортировки (метод Хоара) на языке "Паскаль"
procedure quick(item:^char; left,right:integer);
var
i,j:Integer;
x,y:char; begin
i:=left;
j:=right;
x:=item[int((left+right)/2)];
repeat
while (item[i]<x) and (i<right) do
i:=i+1;
while (x<item[j]) and (j>left) do
j:=j-1;
if i<=j then
begin
y:=item[i];
item[i]:=item[j];
item[j]:=y;
i:=i+1;
j:=j-1;
end;
until i<j;
if left<j then
quick(item,left,j);
if i<right then
quick(item,i,right);
end.
Изменение массива при сортировке по алгоритму Хоара будет имеет вид:
f , d , a , c , b , e
e , d , a , c , b , f
b , c , a , d , e , f
a , b , c , d , e , f
Для оптимальной сортировки в качестве компаранда следует выбрать элемент, расположенный точно в середине диапазона значений текущего подмассива. Однако для большинства наборов данных поиск такого элемента может вылиться в самостоятельную сортировку.
Характеристики: Среднее число сравнений NLog2N, среднее число перестановок N/6*Log2N.
У этого алгоритма есть одна особенность: если для каждого текущего подмассива компандором является текущий максимум, то алгоритм становится N-квадратичным. Однако вероятность этого невысока.
Двоичные деревья
Типы деревьев: Двоичные (бинарные), ориентированные, упорядоченные, мультивариантные (дерево Байера).
Дерево - динамическая нелинейная структура данных, каждый элемент которой содержит собственно информацию (или ссылку на то место в памяти ЭВМ, гди хранится информация) и ссылки на несколько (не менее двух) других таких же элементов. Для бинарного дерева таких ссылок две: на правый соседний и левый соседний элементы.
Основные операции, выполняемые над деревьями (те же, что и над списками) - вставка, удаление и поиск элементов.
Преимущество бинарных деревьев: в случае, если дерево отсортировано, то операция поиска выполняется быстро, с эффективностью, близкой к эффективности двоичного поиска.
Чем же отличается бинарное дерево от двусвязного списка?
Иногда ничем, не только от двусвязного, но и от односвязного списка.
Основное отличие - у списка соседними являются предшествующий и последующий элементы, и структура линейна; а у бинарного дерева соседними являются элементы с меньшим и большим ключом, и структура, в общем случае ветвящаяся - в виде дерева, откуда она и получила свое название.
Нужно помнить, что дерево - это только метод логической организации информации в памяти, а память - линейна. В случае, если информация хранится в произвольном (и неизвестном программисту) месте памяти, а ключ и информация - разные понятия (иногда они могут и совпадать), структура элемента дерева может быть представлена следующим образом:
Этой структуре соответствует набор типов языка Паскаль:
type
info=(* тип хранимых данных *);
ptr=^node;
node=record
key:Integer;
left,right:ptr;
data:^info
end;
var
tree:ptr;
Бинарное дерево, образованное такими элементами показано там же.
Элемент дерева получил название "узел" (node), иногда его называют листом. Единственный начальный элемент (откуда дерево развивается) - корень (root). Фрагмент (часть) дерева - поддерево или ветвь. Узел, от которого не отходят ветви - конечный или терминальный узел. Количество уровней - высота дерева.
Применение деревьев: для хранения информации, как таковой; в процедурах поиска; для организации файлов на дисковых носителях; в построении эффективных кодов для сжатия информации (коды Шеннона-Фано и Хаффмэна).
Рассмотрим принцип построения дерева при занесении в него информации. Пусть последовательно вводятся записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86, 82.
1. Корень - 70;
2. 60<70, следовательно новый узел будет расположен слева от 70;
3. 85>70, следовательно новый узел будет расположен справа от 70;
4. 87>70, следовательно 87 будет находиться в правой ветви; 87>85, следовательно 87 будет расположен справа от 85. И т. д.
При поступлении очередной записи с ключом k, k сравнивают, начиная с корня, с ключом очередного узла. В зависимости от результата сравнения, процесс продолжают в левой или правой ветви до тех пор, пока не будет достигнут один из узлов, с которым можно связать входящую запись. В зависимости от результата сравнения входящего ключа с ключом этого узла, входящая запись будет размещена слева или справа от него и станет новым терминальным узлом.
Порядок следования узлов дерева зависит от того, каким образом нужно организовать доступ к узлам. Процесс получения доступа ко всем узлам - прохождение дерева.
Существует три способа прохождения дерева:
1. Последовательный - дерево проходится, начиная с левой ветви вверх к корню, затем к правой ветви;
2. Нисходящий - от корня к левой ветви, затем к правой;
3. Восходящий - проходится левая ветвь, затем правая, затем корень.
Под корнем здесь понимается как корень всего дерева, так и корень текущей ветви (поддерева).
Хотя бинарное дерево не обязательно должно быть отсортировано, в большинстве практических случаев это требуется.
Порядок сортировки дерева определяется методом, которым дерево будет проходиться.
Максимальный эффект использования дерева достигается, если оно сбалансировано - когда все узлы, кроме терминальных, имеют и правого, и левого соседа; все поддеревья, начинающиеся с одного и того же уровня, имеют одинаковую высоту.
Сбалансированное бинарное дерево - максимально широкое и низкое.
Обратный случай - вырожденное дерево - выродившееся в линейный односвязный список. Такое дерево получается, если заносимые в него данные упорядочены по-возрастанию, или по-убыванию.
Если данные случайны, то получается дерево, приближенное к сбалансированному.
Дерево - рекурсивная структура данных, так как любое поддерево - это тоже дерево. В связи с этим, наиболее эффективными при работе с деревьями оказываются рекурсивные процедуры. Хотя возможно применение и процедур без рекурсии. Рассмотрим разные варианты построения этих процедур.
Рекурсивная процедура добавления узла в дерево на языке "Паскаль"
procedure addnode_r(r,prev:ptr; newkey:integer);
begin
if r=nil then
begin
new(r);
r^.left:=nil;
r^.right:=nil;
r^.key:=newkey;
if tree=nil then
tree:=r; {Первый узел}
else
begin
if newkey<prev^.key then
prev^.left:=r
else
prev^.right:=r
end;
exit
end;
if newkey<r^.key then
addnode_r(r^.left,r,newkey)
else
addnode_r(r^.right,r,newkey)
end;
Процедура вставляет информацию в бинарное дерево, отслеживая ссылки на узлы и выбирая левые или правые ветви, в зависимости от ключа, пока не будет найдено соответствующее место в иерархии дерева.
Аргументы процедуры:
· указатель на корень дерева или ветви, в которм ищется место для нового узла;
· указатель на предыдущий узел;
· ключ;
· сохраняемые данные или указатель на них.
При первом вызове второй аргумент может быть равен nil.
Фактически этот процесс сортирует ключ, прежде чем добавить узел в дерево. Это вариант алгоритма сортировки матодом простых вставок. При построении нового дерева или обслуживании уже упорядоченного дерева рекомендуется добавлять новые узлы именно такой процедурой.
Рекурсивная функция построения идеально сбалансированного дерева с заданным числом узлов на языке "Паскаль"
function maketree(n_node:integer):ptr;
var
newnode:ptr;
newkey,nl,nr:integer;
begin
if n_node=0 then
newnode:=nil
else
begin
nl:=n_node div 2;
nr:=n_node-nl-1;
{Ввод ключа и данных}
read(newkey);
new(newnode);
with newnode^ do
begin
key:=newkey;
left:=maketree(nl);
right:=maketree(nr)
end;
end;
maketree:=newnode
end;
read(n);
tree:=maketree(n);
{Первый вызов}
Рекурсивные процедуры прохождения дерева в последовательном (inorder), нисходящем (preorder) и восходящем (postorder) порядках на языке "Паскаль"
procedure inorder(r:ptr);
begin
if r=nil then exit;
inorder(r^.left);
writeln( ... ); {Вывод информации}
inorder(r^.right)
end;
procedure preorder(r:ptr);
begin
if r=nil then exit;
writeln( ... ); {Вывод информации}
preorder(r^.left);
preorder(r^.right)
end;
procedure postorder(r:ptr);
begin
if r=nil then exit;
postorder(r^.left);
postorder(r^.right)
writeln( ... ); {Вывод информации}
end;
Аргумент этих процедур - указатель на корень ветви, которую требуется найти. Если нужно найти все дерево, необходим указатель на корень дерева. Выход из рекурсивной процедуры происходит, когда встречается терминальный узел.
Возможно добавление нового узла в дерево и без использования рекурсии:
Нерекурсивная процедура добавления нового узла в дерево на языке "Паскаль"
procedure addnode2(skey:integer; var tree:ptr; newdata:^info);
var
r,s:ptr;
t:^info;
begin
if not searchtree(skey,tree,r) then
begin
new(t); {Занесение}
t:=newdata; {данных}
new(s); {новый}
s^.key:=skey;
s^.left:=nil; {узел}
s^.right:=nil;
s^.data:=t;
if tree=nil then
tree:=s
else
if skey<r^.key then
r^.left:=s
else
r^.right:=s
end
end;
Поиск в бинарных деревьях выполняется достаточно просто:
Программа поиска в бинарномдереве на языке "Паскаль"
function search_tree(skey:integer; var tree,fnode:ptr):boolean;
var
p,q:ptr;
b:boolean;
begin
b:=false;
p:=tree;
if tree<>nil then
repeat
q:=p;
if p^.key=skey then
b:=true
else
begin
if skey<p^.key then
p:=p^.left
else
p:=p^.right
end
until (b) or (p=nil);
search_tree:=b;
fnode:=q;
end;
Длительность поиска зависит от структуры дерева. Для сбалансированного дерева (изображено на рисунке) поиск аналогичен двоичному - то есть нужно посмотреть не более Log2N узлов.
Для вырожденного дерева (изображено на рисунке) поиск аналогичен поиску в односвязном списке - всреднем нужно посмотрет половину узлов.
Удаление узла из дерева - существенно более сложный процесс, чем поиск, так как удаляемый узел может быть корневым, левым или правым. Узел может давать начало другим деревьям (их может быть от 0 до двух).
Наиболее простым случаем является удаление терминального узла, или узла, из которого выходит только одна ветвь.
Для этого достаточно скорректировать соответствующий указатель у предшествующего узла.
Наиболее трудный случай - удаление корневого узла поддерева с двумя ветвями, поскольку приходится корректировать несколько указателей. Нужно найти подходящий узел, который можно было бы вставить на место удаляемого, причем этот подходящий узел должен просто перемещаться. Такой узел всегда существует.
Если это самый правый узел левого поддерева, то для достижения этого узла нужно перейти в следующий от удаляемого узел по левой ветви, а затем переходить в очередные узлы только по левой ветви до тех пор, пока очередной левый указатель не будет равен nil.
Такой узел может иметь не более одной ветви.
Пример удаления из дерева узла с ключом 50.
Процедура удаления узла должна различать три случая:
узла с данным ключом в дереве нет;
узел с заданным ключом имеет не более одной ветви;
узел с заданным ключом имеет две ветви.
Процедура удаления узла
Процедура удаления узла двоичного дерева на языке "Паскаль"
procedure delnode(var d:ptr; key:integer);
var
q:ptr;
procedure del1(var r:ptr);
begin
if r^.right=nil then
begin
q^.key:=r^.key;
q^.data:=r^.data;
q:=r;
r:=r^.left
end
else
del1(r^.right)
end;
begin
if d=nil then exit {Первый случай}
else
if key<d^.key then
delnode(d^.left,key)
else
if key>d^.key then
delnode(d^.right,key)
else
begin
q:=d; {Второй случай}
if q^.right=nil then
d:=q^.left
else
if q^.left=nil then
d:=q^.right
else {Третий случай}
del1(q^.left)
end
end;
Вспомогательная рекурсивная процедура del1 вызывается только в третьем случае. Она проходит дерево до самого правого узла левого поддерева, начиная с удаляемого узла q^, и заменяет значения полей key и data в q^ соответствующими записями полей узла r^. После этого узел, на который указывает r можно исключить (r:=r^.left).
Таблицы
Таблица - некоторый (вообще говоря неупорядоченный) набор именованных записей. Имена могут выбираться достаточно произвольным образом, но чтобы можно было организовать эффективный поиск записи по ее имени, нужно сравнивать любые два имени записей и устанавливать, какое из них больше, а какое меньше. Имя записи в таблице называется ключом записи.
Часто в качестве ключей используются целые положительные числа. Можно использовать строки. Над типом данных, используемым для представления ключа, должны быть определены операции сравнения. Если встроенных операций нет, можно разработать функции, сравнивающие ключи.
Операции, определенные над таблицей, как структурой данных:
поиск записи с заданным ключом;
включение в таблицу запиаи с заданным ключом (обычно считается, что если в таблице уже есть запись с таким ключом, то старые значения заменяются новыми);
удаление записи из таблицы.
Существует несколько способов организации таблицы. Выбор того или иного способа определяется характером использования таблицы:
Односвязный список.
Простейший способ представления таблицы.
Достоинства:
кроме полезной информации присутствует только один указатель на следующую запись, следовательно, память ЭВМ используется достаточно эффективно;
алгоритм перебора при поиске очень прост;
включение в таблицу заведомо новой записи можно сделать максимально эффективно, помещая новую запись в фиксированое место таблицы, например, в начало или в конец.
Недостатки:
основной недостаток заключается в том, что поиск может оказаться длительным, так как для неупорядоченного списка возможен (практически) только последовательный поиск. В среднем случае просматривается половина записей, а в худьшем - все. Если число записей N невелико, то неэффективностью поиска можно принебречь, отдав предпочтение простоте алгоритма и быстродействию. Если N велико - то наоборот;
даже если исконной записи нет, то для установления этого факта при поиске придется пересмотреть всю таблицу.
Упорядоченный список.
Записи в таблице расположены в порядке возрастания или убывания ключей. В этом случае неудачный поиск можно прекратить при достижении записи с ключем больше (если ключи отсортированы в порядке возрастания) заданного.
Усложняется процедура включения новой записи в таблицу, так как должна поддерживаться упорядоченность, а следовательно, предворительнонужно найти соответствующее место для вставки записи.
Достоинство:
упорядоченнй список позволяет использовать двоичный поиск.
Массив записей.
В каждой записи хранится ключ и указатель на полезную информацию. Так как размер записей одинаков, их можно объединить в массив, упорядочив по-возрастанию ключей. Следовательно, массив - это упорядоченный список с разорванными связями.
Достоинства:
двоичный поиск;
очень быстрый доступ при индексации массива.
Недостатки:
плохо подходит для включения и удаления записей, так как связи разорваны и приходится сдвигать все элементы массива;
может применяться лишь для таблиц фиксированного размера.
Двоичное дерево.
Достоинство:
Наиболее эффективная реализация операций.
Недостаток:
Сложность некоторых операций (поддержание сбалансированного дерева, удаление узла из дерева).