Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Древесная сортировка
|
|
Древесная сортировка избегает необходимости каждый раз находить максимальный элемент. При следовании этому методу постоянно поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться в A[1]. Сортировка называется древесной, потому что в этом методе используется структура данных, называемая двоичным деревом.
Двоичное дерево имеет элемент, называемый корнем. Корень, как и любой другой элемент дерева (называемый вершиной), может иметь до двух элементов-сыновей. Все элементы, кроме корневого имеют элемент-родитель.
Условимся нумеровать вершины числами 1, 2,...: сыновьями вершины с номером k будут вершины с номерами 2*k и 2*k+1, - как это сделано на рисунке. Как можно заметить, двоичное разложение номера вершины указывает путь к этой вершине от корня (0 - к левому сыну, 1 - к правому сыну). Например, 910=10012. Первую 1 двоичного разложения пропускаем (в начале всегда стоит 1). Затем идет 0, то есть от корня переходим к левому сыну (вершина номер 210=102), потом снова 0 - переходим к левому сыну (вершина номер 410=1002), последней следует цифра 1 - переходим к правому сыну и как раз попадаем в вершину номер 910=10012. Значит номер элемента однозначно определяет его положение в дереве.
Введенный способ нумерации вершин дерева позволяет хранить деревья в массиве, где индекс массива будет номером вершины.
Пусть A[1]..A[n] - массив, подлежащий сортировке. Вершинами дерева будут числа от 1 до n; о числе A[i] мы будем говорить как о числе, стоящем в вершине i. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем хранить в переменной k. Таким образом, в процессе работы алгоритма массив A[1]..A[n] делится на две части: в A[1]..A[k] хранятся числа на дереве, а в A[k+1].. A[n] хранится уже отсортированная в порядке возрастания часть массива - элементы, уже занявшие свое законное место.
На каждом шаге алгоритм будет изымать максимальный элемент дерева и помещать его в отсортированную часть, на освободившееся в результате сокращения дерева место.
Договоримся о терминологии. Вершинами дерева считаются числа от 1 до текущего значения переменной k. У каждой вершины s могут быть сыновья 2*s и 2*s+1. Если оба этих числа больше k, то сыновей нет; такая вершина называется листом. Если 2*s=k, то вершина s имеет ровно одного сына (2*s).
Для каждого s из 1..k рассмотрим " поддерево" с корнем в s: оно содержит вершину s и всех ее потомков (сыновей, сыновей сыновей и т.д. - до тех пор, пока мы не выйдем из отрезка 1..k).
Вершину s будем называть регулярной, если стоящее в ней число - максимальный элемент s-поддерева; s-поддерево назовем регулярным, если все его вершины регулярны. (В частности, любой лист образует регулярное одноэлементное поддерево.)
Схема алгоритма такова:
k: = n... Сделать 1-поддерево регулярным; while k< > 1 dobegin... обменять местами A[1] и A[k]; k: = k - 1; {A[1]..A[k-1] < = A[k] < =...< = A[n]; 1-поддерево регулярно везде, кроме, возможно, самого корня }... восстановить регулярность 1-поддерева всюдуend;В качестве вспомогательной процедуры нам понадобится процедура восстановления регулярности s-поддерева в корне. Вот она:
{s-поддерево регулярно везде, кроме, возможно, корня}t: = s; {s-поддерево регулярно везде, кроме, возможно, вершины t}while ((2*t+1< =k) and (A[2*t+1]> A[t])) or ((2*t< =k) and (A[2*t]> A[t])) dobegin if (2*t+1< =k) and (A[2*t+1]> =A[2*t]) then begin... обменять A[t] и A[2*t+1]; t: = 2*t + 1; end else begin... обменять A[t] и A[2*t]; t: = 2*t; end; end;Чтобы убедиться в правильности этой процедуры, посмотрим на нее повнимательнее. Пусть в s-поддереве все вершины, кроме разве что вершины t, регулярны. Рассмотрим сыновей вершины t. Они регулярны, и потому содержат наибольшие числа в своих поддеревьях. Таким образом, на роль наибольшего числа в t-поддереве могут претендовать число в самой вершине t и числа, содержащиеся в ее сыновьях. (В первом случае вершина t регулярна, и все в порядке.) В этих терминах цикл можно записать так:
while наибольшее число не в t, а в одном из сыновей dobegin if оно в правом сыне then begin...поменять t с ее правым сыном; t: = правый сын end else begin {наибольшее число - в левом сыне}...поменять t с ее левым сыном; t: = левый сын endendПосле обмена вершина t становится регулярной (в нее попадает максимальное число t-поддерева). Не принявший участия в обмене сын остается регулярным, а принявший участие может и не быть регулярным. В остальных вершинах s-поддерева не изменились ни числа, ни поддеревья их потомков (разве что два элемента поддерева переставились), так что регулярность не нарушилась.
Эта же процедура может использоваться для того, чтобы сделать 1-поддерево регулярным на начальной стадии сортировки:
k: = n; u: = n; {все s-поддеревья с s> u регулярны }while u< > 0 dobegin {u-поддерево регулярно везде, кроме разве что корня}... восстановить регулярность u-поддерева в корне; u: =u-1; end;Теперь запишем процедуру сортировки на паскале:
Преимущество этого метода перед другими в том, что он, имея Tmax(n*log(n)) (внутри внешнего цикла зависящего от n линейно вызывается процедура Restore, требующая порядка log(n) действий), при сортировке не требует дополнительной памяти порядка n.