IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

> Методы сортировок
сообщение
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 419
Пол: Мужской

Репутация: -  6  +


Описание и реализация алгоритмов:
****** ******


Сравнительная скорость работы некоторых нижеприведенных алгоритмов сортировки:

Прикрепленное изображение

Примечание:

size: размер сортируемой последовательности
n: количество сортировок для замера времени
*: RadixSort в последнем тесте прогонялся при параметрах: size=21000; n=100
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Гость






Древесная сортировка (TreeSort)

Использует Двоичные (бинарные) деревья, в которых для каждого предшественника выполнено следующее правило: левый преемник всегда меньше, а правый преемник всегда больше или равен предшественнику.

При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом вставляя на место: если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить.

Если мы будем рекурсивно обходить дерево по правилу "левый сын -> родитель -> правый сын", то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. Hа этом и основана идея сортировки деревом.

Более подробно правило обхода можно сформулировать так: обойти левое поддерево -> вывести корень -> обойти правое поддерево, где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.

Const n = 8;
Type
TType = Integer;
arrType = Array[1 .. n] Of TType;

Const
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);

(* Сортировка с помощью бинарного дерева *)
Type
PTTree = ^TTree;
TTree = Record
a: TType;
left, right: PTTree;
End;

{ Добавление очередного элемента в дерево }
Function AddToTree(root: PTTree; nValue: TType): PTTree;
Begin
(* При отсутствии преемника создать новый элемент *)
If root = nil Then Begin
root := New(PTTree);
root^.a := nValue;
root^.left := nil;
root^.right := nil;
AddToTree := root; Exit
End;

If root^.a < nValue Then
root^.right := AddToTree(root^.right, nValue)
Else
root^.left := AddToTree(root^.left, nValue);
AddToTree := root
End;


(* Заполнение массива *)
Procedure TreeToArray(root: PTTree; Var a: arrType);
Const maxTwo: Integer = 1;
Begin
(* При отсутствии преемников рекурсия остановится *)
If root = nil Then Exit;

(* Левое поддерево *)
TreeToArray(root^.left, a);
a[maxTwo] := root^.a; Inc(maxTwo);

(* Правое поддерево *)
TreeToArray(root^.right, a);
Dispose(root)
End;

(* Собственно процедура сортировки *)
Procedure SortTree(Var a: arrType; n: Integer);
Var
root: PTTree;
i: Integer;
Begin
root := nil;
For i := 1 To n Do
root := AddToTree(root, a[i]);
TreeToArray(root, a)
End;

Var i: Integer;
Begin
WriteLn('До сортировки:')
For i := 1 To n Do Write(a[i]:4);
WriteLn;

SortTree(a, n);

WriteLn('После сортировки:')
For i := 1 To n Do Write(a[i]:4);
WriteLn
End.


Общее быстродействие метода O(n*logn). Поведение неестественно, устойчивости, вообще говоря, нет.
Основной недостаток этого метода - большие требования к памяти под дерево. Очевидно, нужно n места под ключи и, кроме того, память на 2 указателя для каждого из них.

Поэтому TreeSort обычно применяют там, где:
  1. построенное дерево можно с успехом применить для других задач;
  2. данные уже построены в "дерево";
  3. данные можно считывать непосредственно в дерево. Hапример, при потоковом вводе с консоли или из файла.
Т.е. там, где не требуется дополнительной памяти...


Прикрепленные файлы
Прикрепленный файл  TRE_SORT.PAS ( 1.43 килобайт ) Кол-во скачиваний: 1352
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 20.01.2022 11:14
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name