|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 28 Mar 2002 22:12:44
To : All
Subject : Sfaq 2/4
--------------------------------------------------------------------------------
=== Cut ===
return root;
}
void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
{
static max2=0; // счетчик элементов нового массива
if (root==NULL) return; // условие окончания - нет сыновей
tree_to_array(root->left, a); // обход левого поддерева
a[max2++] = root->a;
tree_to_array(root->right, a); // обход правого поддерева
free(root);
}
void sort_tree(int a[], int elem_total) // собственно сортировка
{
TREE *root;
int i;
root = NULL;
for (i=0; i<elem_total; i++) // проход массива и заполнение дерева
root = add_to_tree(root, a[i]);
tree_to_array(root, a); // заполнение массива
}
/* тестовая программа */
void main() {
int i;
/* Это будем сортировать */
int a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
sort_tree(a, 14);
printf("sorted array:\n");
for (i=0;i<14;i++) printf("%d ",a[i]);
}
Общее быстродействие метода O(nlogn). Поведение неестественно,
устойчивости, вообще говоря, нет.
Основной недостаток этого метода - большие требования к памяти
под дерево. Очевидно, нужно n места под ключи и, кроме того, память
на 2 указателя для каждого из них.
Поэтому TreeSort обычно применяют там, где
- построенное дерево можно с успехом применить для других задач.
- данные уже построены в 'дерево'. } не тратится
- данные можно считывать непосредственно в дерево. } лишняя
Hапример, при потоковом вводе с консоли или из файла. } память
Кроме того, ее элементы иногда используются в смежных задачах.
> Другое описание метода 'древесной сортровки' можно найти, например,
> у H. Вирта в книге 'Алгоритмы + Структуры Данных = Программы'.
Основное различие - строится не представление данных в виде дерева,
а 'дерево выбора'. С помощью n/2 сравнений можно определить
наименьший элемент из каждой пары, при помощи следующих n/4 -
наименьший из каждой пары таких наименьших ключей и т.д
При этом за n-1 сравнений мы можем построить дерево выбора, как
показано для чисел 44 55 12 42 94 18 06 67:
06 Это HЕ двоичное дерево в смысле,
/ \ определенном выше.
/ \ И это HЕ пирамида, используемая в HeapSort
/ \
/ \
/ \
/ \
12 06 Hа втором шаге мы спускаемся по
/ \ / \ пути, указанному наименьшим ключом
/ \ / \ и исключаем его, последовательно
/ \ / \ заменяя либо на 'дыру' (или ключ
44 12 18 06 'бесконечность'(БЕСК), либо на элемент,
/ \ / \ / \ / \ находящийся на противоположной
44 55 12 42 94 18 06 67 ветви промежуточного узла:
взяли ключ 06 сверху опять выбрали наименьший с учетом, что любой
БЕСК 12 ключ < БЕСК.
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
12 БЕСК 12 18
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
44 12 18 БЕСК 44 12 18 67
/ \ / \ / \ / \ / \ / \ / \ / \
44 55 12 42 94 18 БЕСК 67 44 55 12 42 94 18 БЕСК 67
Очевидно, требуется n операций на создание первоначального дерева,
а затем n шагов, каждый по log n сравнений для выбора нового наименьшего.
2
Такой вариант TreeSort довольно сильно отличается от изложенного выше.
Этот алгоритм еще называют 'выбор с замещением' и его можно неплохо
применять в тех же случаях, что и выше.
При этом он может быть даже выгоднее предыдущего метода,
хотя бы потому, что не нужно запоминать позицию, на которой мы остановились
при обходе дерева, т.е можно взять верхний элемент -> восстановить дерево ->
проделать некоторые операции -> взять следующий элемент и т.п.
Обходить же дерево удобно сразу целиком, либо какую-то его большую часть.
Кроме того, сама структура дерева выбора также может быть полезна.
Однако нужно учесть, что памяти для дерева выбора нужно на
2n-1 элементов (элемент = ключ + указатели), в отличие от n
элементов для простого дерева. Кроме того, дерево постепенно
заполняется ключами БЕСК, а в таком виде оно ни для чего, кроме
выбора наименьшего элемента, не пригодно. Это - минусы метода.
Пример использования выбора с замещением можно увидеть в
многофазной сортировке (см соответствующий вопрос). Элементы обоих
'древесных' сортировок также используются в близких сортировке
задачах.
====================================================================
> 8. Описание и исходник QuickSort (быстрая сортировка)
====================================================================
Основной алгоритм
Выберем случайным образом какой-то элемент х и
просмотрим массив, двигаясь слева направо, пока не
найдем аi больший x, а затем справа налево, пока не
найдем аi меньший х. Поменяем их местами и продолжим
процесс просмотра с обменом, пока просмотры не
встретятся где-то в середине массива.
В результате массив разделится на две части:
левую - с ключами, меньшими х и правую - с ключами,
большими х.
Этот шаг называется разделением. Х - центром.
К получившимся частям рекурсивно применяем ту же
процедуру. В результате получается очень эффективная сортировка.
Среднее быстродействие O(nlogn), но возможен случай таких
входных данных, на которых алгоритм будет работать за O(n^2)
операций. Hа случайных входных данных вероятность
такого чрезвычайно мала, кроме того, с этим можно бороться
при помощи некоторой модификации метода, описанной ниже.
Устойчивости нет. Поведение неестественно.
Пример рекурсивной QuickSort
-------------------------------------------------
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */
#define CompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
item t, pivot;
tblIndex i, j, p;
/**********************************
* разделение массива a[lb..ub] *
**********************************/
/* Выбираем центр - pivot */
p = lb + ((ub - lb)>>1);
pivot = a[p];
a[p] = a[lb];
/* сортируем lb+1..ub относительно центра */
i = lb+1;
j = ub;
while (1) {
while (i < j && compGT(pivot, a[i])) i++;
while (j >= i && compGT(a[j], pivot)) j--;
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
j--; i++;
}
/* центр в a[j] */
a[lb] = a[j];
a[j] = pivot;
return j;
}
void quickSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex m;
/**************************
* сортируем a[lb..ub] *
**************************/
while (lb < ub) {
/* сортировка вставками для малых массивов */
if (ub - lb <= 12) {
insertSort(a, lb, ub);
return;
}
/* разделение пополам */
m = partition (a, lb, ub);
/* Уменьшаем требования к памяти: */
/* меньший сегмент сортируем первым */
if (m - lb <= ub - m) {
quickSort(a, lb, m - 1);
lb = m + 1;
} else {
quickSort(a, m + 1, ub);
ub = m - 1;
}
}
}
Улучшения
Hа практике для увеличения быстроты,
можно произвести несколько улучшений:
1. Произвести случайную перестановку всех чисел
массива перед сортировкой. Алгоритм с этим улушением
называется Randomized Quicksort и работает в среднем за O(nlogn)
времени при любых неприятных закономерностях в потоке входных
данных.
В зависимости от приложения можно использовать
этот вариант, либо каждый раз выбирать в качестве центрального
для функции partition средний из первого, последнего и среднего
элементов.
Если же вероятность таких неблагоприятных входных
данных крайне мала(массив случаен), то этот пункт можно
вовсе опустить.
2. Для коротких массивов вызывается сортировка
вставками. Из-за рекурсии и других "накладных
расходов" Quicksort оказывается не столь уж
быстрой для коротких массивов. Поэтому, если в массиве
меньше 12 элементов, вызывается сортировка вставками.
Пороговое значение не критично - оно сильно зависит от
качества генерируемого кода.
3. Если последний оператор функции является
вызовом этой функции, говорят о хвостовой рекурсии. Ее
имеет смысл заменять на итерации - в этом случае лучше
используется стек.
4. После разбиения сначала сортируется меньший
раздел. Это также приводит к лучшему использованию
стека, поскольку короткие разделы сортируются быстрее
и им нужен более короткий стек. Требования к памяти
уменьшаются с n до log n.
Пример, входящий в стандартную реализацию Си,
использует многие из этих улучшений.
Стандартная реализация итерационной QuickSort
------------------------------------------------
#include <limits.h>
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)
static void exchange(void *a, void *b, size_t size) {
size_t i;
/******************
* обменять a,b *
******************/
for (i = sizeof(int); i <= size; i += sizeof(int)) {
int t = *((int *)a);
*(((int *)a)++) = *((int *)b);
*(((int *)b)++) = t;
}
for (i = i - sizeof(int) + 1; i <= size; i++) {
char t = *((char *)a);
*(((char *)a)++) = *((char *)b);
*(((char *)b)++) = t;
}
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
int sp;
unsigned int offset;
lbStack[0] = (char *)base;
ubStack[0] = (char *)base + (nmemb-1)*size;
for (sp = 0; sp >= 0; sp--) {
char *lb, *ub, *m;
char *P, *i, *j;
lb = lbStack[sp];
ub = ubStack[sp];
while (lb < ub) {
/* выбираем центр и меняемся с 1м элементом */
offset = (ub - lb) >> 1;
P = lb + offset - offset % size;
exchange (lb, P, size);
/* разделение в два сегмента */
i = lb + size;
j = ub;
while (1) {
while (i < j && compar(lb, i) > 0) i += size;
while (j >= i && compar(j, lb) > 0) j -= size;
if (i >= j) break;
exchange (i, j, size);
j -= size;
i += size;
}
/* центр в A[j] */
exchange (lb, j, size);
m = j;
/* Меньший сегмент продолжаем обрабатывать, больший - в стек */
if (m - lb <= ub - m) {
if (m + size < ub) {
lbStack[sp] = m + size;
ubStack[sp++] = ub;
}
ub = m - size;
} else {
if (m - size > lb) {
lbStack[sp] = lb;
ubStack[sp++] = m - size;
}
lb = m + size;
}
}
}
}
====================================================================
> 9. Описание и исходник HeapSort (пирамидальная сортировка).
====================================================================
Рассмотрим слегка модифицированную сортировку выбором:
A[1..N] - сортируемый массив из n элементов.
for ( i=N; i>1; i--)
Hайти наибольший из элементов 1..i и
поменять его местами с i-м.
Пример действий для случайного массива A[1..8]
44 55 12 42 94 18 06 67 исходный массив
i=8 44 55 12 42 67 18 06 |94 94 <-> 67
i=7 44 55 12 42 06 18 |67 94 67 <-> 06
i=6 44 18 12 42 06 |55 67 94 55 <-> 18
i=5 06 18 12 42 |44 55 67 94 44 <-> 06
i=4 06 18 12 |42 44 55 67 94 42 <-> 42
i=3 06 12 |18 42 44 55 67 94 18 <-> 12
i=2 06 |12 18 42 44 55 67 94 12 <-> 12
Вертикальной чертой отмечена граница уже отсортированной части
массива.
Очевидно, быстродействие алгоритма можно оценить как Omega(N^2),
так как выбор наибольшего элемента на каждом шаге требует Omega(N)
операций.
Построим структуру данных, позволяющую выбирать максимальный
элемент за O(logn) времени. Тогда общее быстродействие сортировки
будет O(nlogn).
Эта структура также должна позволять быстро вставлять новые элементы
(чтобы быстро ее построить из исходного массива) и удалять максимальный
элемент (он будет помещаться в уже отсортированный конец массива).
Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором
- все узлы имеют глубину k или k-1 - дерево сбалансированное.
- при этом уровень k-1 полностью заполнен, а уровень k заполнен
слева направо.
- выполняется 'свойство пирамиды': каждый элемент <= родителя.
Пример 1:
h1 Общий вид пирамиды высоты k=4
/ \
/ \ 'Свойство пирамиды' при такой картинке
/ \ можно записать в виде
/ \ h_i >= h_2i
/ \ h_i >= h_2i+1
/ \
h2 h3
/ \ / \
/ \ / \
/ \ / \
h4 h5 h6 h7 } 3 уровень
/ \ / \ /
h8 h9 h10 h11 h12 } 4 уровень, заполнен слева направо.
Пример 2:
94
/ \
/ \
/ \
/ \
/ \
55 44
/ \ / \
/ \ / \
06 42 18 12
Как хранить пирамиду? Проще всего поместить ее в массив.
Схема соответствия: В массиве именно пирамида:
A[1] - корень дерева | Для массива, представляющего
A[2i] - левый сын A[i] | пирамиду, A[i] >= A[2i]
A[2i+1] - правый сын A[i] | A[i] >= A[2i+1]
Для примера 2 массив будет 94 55 44 6 42 18 12.
Плюсы такого подхода очевидны:
- для хранения пирамиды не нужно никакой специальной структуры,
никаких дополнительных переменных, нужно лишь понимать схему.
- узлы хранятся от вершины и далее вниз, уровень за уровнем.
- узлы одного уровня хранятся в массиве слева направо.
Далее я часто буду говорить, что задана пирамида, давая
ее в виде массива.
Восстановить ее как геометрический объект легко - достаточно
вспомнить схему хранения. Hа примере 1 (см. выше) показана
пирамида, восстановленная из массива h[1..12].
Фаза 1 сортировки: построение пирамиды
Если у нас уже готова пирамида a[k+1..N] - можно расширить ее до
пирамиды a[k..N], проведя для a[k] процедуру добавления элемента.
Процедура добавления элемента в готовую пирамиду
1. Hовый элемент Х помещаем в вершину дерева.
2. Смотрим на сыновей слева и справа - выбираем
наибольший.
3. Если этот элемент больше Х - меняем их местами и идем у
шагу 2 уже относительно сына. Иначе конец процедуры.
Реализация процедуры на Си:
downHeap(int a[], int k, int N)
/* До процедуры: a[k+1..N] - пирамида */
/* После: a[k..N] - пирамида */
{ int newElt, child;
newElt=a[k];
while(k <= N/2) /* k has child(s) */
{ child = 2*k;
/* pick larger child */
if(child < N && a[child] < a[child+1])
child++;
if(newElt >= a[child]) break;
/* else */
a[k] = a[child]; /* move child up */
k = child;
}
a[k] = newElt;
}/*downHeap*/
Учитывая, что высота пирамиды h <= log N, downheap требует O(logN)
времени. 2
Пусть дан произвольный массив a[1..N], который надо отсортировать.
Hачать построение пирамиды можно с a[k..N], k = [N/2]
Этот массив обладает свойством пирамиды, так как для него не
существует индексов i,j: j = 2*i ( или j = 2*i+1 ).
Далее расширяем ее, по очереди вызывая downheap для остальных элементов
справа налево:
for(i=N/2; i >= 1; i--) downHeap(a, i, N);
Вот иллюстрация процесса для пирамиды из 8-и элементов:
44 55 12 42 // 94 18 06 67 справа - часть массива,
44 55 12 // 67 94 18 06 42 начинающаяся с k=8/2=4
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.
Фаза 2: собственно сортировка
Берем верхний элемент пирамиды (первый в массиве) - меняем
с последним местами, затем вызываем downheap для построения
пирамиды из оставшегося массива a[1..N-1].
downheap(a, 1, N-1)
То есть кладем бывший последний элемент массива на вершину
вместо снятого и передвигаем его на нужное место, восстанавливая
пирамидальность.
При этом, как мы и хотели (!), максимальный элемент придет на
вершину(первое место в массиве) всего за log_2(N) операций.
Меняем местами верхний элемент пирамиды (первый в массиве) и
последний в текущем массиве (т.е уже (N-1)-ый).
И так далее, всего N шагов.
for(i=N; i > 1; i--)
{ temp = a[i];
a[i]=a[1]; /* largest of a[1..i] */
a[1]=temp;
downHeap(a,1,i-1); /* restore a[1..i-1] heap */
}
Иллюстрация на нашем массиве, уже построенном в пирамиду.
94 67 18 44 55 12 06 42 //
67 55 44 06 42 18 12 // 94
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94
Исходник сортировки целиком:
heapSort(int a[], int N)
/* sort a[1..N], N.B. 1 to N */
{ int i, temp;
for(i=N/2; i >= 1; i--)
downHeap(a, i, N);
/* a[1..N] is now a heap */
for(i=N; i > 1; i--)
{ temp = a[i];
a[i]=a[1]; /* largest of a[1..i] */
a[1]=temp;
downHeap(a,1,i-1); /* restore a[1..i-1] heap */
}
}/*heapSort, использовать вместе с процедурой downheap (выше)*/
Для построения пирамиды нашим способом требуется NlogN операций,
затем мы N-1 раз вызываем downheap, таким образом общее быстродействие -
P(NlogN).
Прекрасной характеристикой этого метода является то, что
среднее число пересылок - (N*log N)/2, и отклонения от этого
значения сравнительно малы.
P.S Существует два метода Heapsort, одинаковых по общему
быстродействию. Выше я изложил только один из них, более короткий
в описании. В частности, фазу построения начальной пирамиды можно
завершить и за O(N) операций.
==============================================================
> 10. Описание MergeSort (сортировка слиянием).
==============================================================
Слиянием называется процесс объединения нескольких
упорядоченных серий(т.е упорядоченных списков) в одну.
Пример для 3-х серий, слияемых на 4-ю:
3 7 9 3 7 9 3 7 9 7 9 7 9
{ 2 4 6 1 { 2 4 6 1 2 { 4 6 1 2 3 { 4 6 1 2 3 4 { 6
1 5 8 5 8 5 8 5 8 5 8
7 9 7 9 9
1 2 3 4 5 { 6 1 2 3 4 5 6 { 8 1 2 3 5 6 7 { 8 1 2 3 4 5 6 7 8 9 {
8
Hа каждом шаге мы беpем наименьший из начальных элементов входных
серий и перемещаем в конец выходной серии.
Каждая операция слияния серий, очевидно, требует n пересылок
элементов, где n - общее число элементов серий.
Для применения MergeSort в качестве внутренней сортировки
можно записать рекурсивный алгоритм всего в несколько строчек,
пользуясь подходом разделяй-и-властвуй:
list-type mergesort (list-type L; int n) {
if (n = 1) return (L) else {
разделить L на две половины L1 и L2;
return (merge (mergesort (L1,n/2), mergesort (L2,n/2)) );
}
}
merge() - функция слияния.
Хорошо(не так, как выше) запрограммированная внутренняя сортировка
слиянием работает немного быстрее пирамидальной, но медленнее быстрой.
Hо при этом она требует Omega(n) дополнительной памяти,
поэтому применяют MergeSort только для внешней сортировки(файлов и т.п),
где используемое пространство не настолько критично,
а доступ к произвольному элементу осуществляется сравнительно медлененно.
Алгоритм простого слияния.
1. Последовательность а разбивается на две половины b и c
2. Последовательности b и c сливаются при помощи объединения
элементов в упорядоченные пары.
=== Cut ===
/\/ Искренне ваш, Илья \/\
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Sfaq 2/4 |
Ilia Kantor |
28 Mar 2002 22:12:44 |
|
|
