|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 10 Jan 2002 22:51:18
To : All
Subject : <без заголовка>
--------------------------------------------------------------------------------
=== Cut ===
/ \
/ \
/ \
/ \
h2 h3
/ \ / \
/ \ / \
h4 h5 h6 h7
/ \ / \ / \ / \
h8 h9h10 h11 h12 h13 h14 h15
Для последовательности 06 42 12 55 94 18 44
06
/ \
/ \
/ \
/ \
/ \
42 12
/ \ / \
/ \ / \
55 94 18 44
Добавление элемента в готовую пирамиду
1. Hовый элемент Х помещаем в вершину дерева.
2. Смотрим на элемент слева и элемент справа - выбираем
наименьший.
3. Если этот элемент меньше Х - меняем их местами и идем у
шагу 2. Иначе конец процедуры.
Фаза 1: построение пирамиды
Пусть дан массив h_1 ... h_n . Ясно, что элементы h_n/2 + 1
... h_n уже образуют 'нижний ряд' пирамиды, так как не
существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То
есть тут упорядочивания не требуется.
Hа каждом шаге добавляется новый элемент слева и
'просеивается' на место. Вот иллюстрация процесса для пирамиды
из 8-и элементов:
44 55 12 42 // 94 18 06 67
44 55 12 // 42 94 18 06 67
44 55 // 06 42 94 18 12 67
44 // 42 06 55 94 18 12 67
// 06 42 12 55 94 18 44 67
Фаза 2: сортировка
Для того, чтобы рассортировать элементы, необходимо
выполнить n шагов просеивания: после каждого шага очередной
элемент берется с вершины пирамиды. Hа каждом шаге берем
последний элемент Х, верхний элемент пирамиды помещается на его
место, а Х просеивается на свое 'законное'. В этом случае
необходимо совершить n - 1 шагов. Пример:
06 42 12 55 94 18 44 67 //
12 42 18 55 94 67 44 // 06
18 42 44 55 94 67 // 12 06
42 55 44 67 94 // 18 12 06
44 55 94 67 // 42 18 12 06
55 67 94 // 44 42 18 12 06
67 94 // 55 44 42 18 12 06
94 // 67 55 44 42 18 12 06
Hу вот мы м получили отсортированную последовательность,
только в обратном порядке. Изменяя сравнения на
противоположные, получаем функцию Heapsort на Паскале
Прекрасной характеристикой этого метода является то, что
среднее число пересылок - (n*log n)/2 и отклонения от этого
значения сравнительно малы.
{ сортируем массив типа 'item' по ключу 'a.key' }
procedure Heapsort;
var i,l: index; x: item;
procedure sift;
label 13;
var i, j: index;
begin i := l; j := 2*i; x := a[i];
while j <= r do
begin if j < r then
if a[j].key < a[j+1].key then j := j+1;
if x.key >= a[j].key then goto 13;
a[i] := a[j]; i := j; j := 2*i
end;
13: a[i] := x
end;
begin l := (n div 2) + 1; r := n;
while l > 1 do
begin l := l - 1; sift
end;
while r > 1 do
begin x := a[l]; a[l] := a[r]; a[r] := x;
r := r - 1; sift
end
end { heapsort }
==============================================================
> 6. Требования QuickSort и HeapSort. InsertSort... Что лучше ?
==============================================================
A: Kantor Ilia
> Простые вставки.
Общее быстродействие - O( n^2 ), но ввиду простоты метода,
является наибыстрейшим для малых ( 12-20 элементов ) массивов.
Естественное поведение. Легко прибавлять новые элементы.
Ввиду своих особенностей, чрезвычайно хорош для списков.
Сортировка не требует дополнительной памяти.
> Быстрая сортировка
Общее быстродействие Quicksort O( nlogn ) времени.
Случай n^2 возможен лишь в теории, но вероятность такого
чрезвычайно мала.
В общем и целом - наиболее быстрая сортировка сравнениями
для разупорядоченных массивов с >50 элементами.
Поведение неестественно. Уже практически отсортированный
массив будет сортироваться столько же, сколько и полностью
разупорядоченный.
В отличие от других методов, требует выделения дополнительной памяти.
Итерационный вариант требует logn памяти, рекурсивный - O(n).
> Пирамидальная сортировка.
В 1.5 раза медленнее быстрой. Общее быстродействие всегда O(nlogn).
Практически, ее элементы часто применяются в смежных задачах.
Поведение неестественно.
Основное достоинство - сортировка не требует дополнительной памяти.
====================================================================
> 7. Какая самая быстрая сортировка ?
====================================================================
A: Kantor Ilia
Давайте разберемся раз и навсегда. Есть два типа сортировок:
Распределяющая и ее вариации | Сортировка сравнениями
|
Основана на том, что число возможных | Пользуется лишь возможностью
значений ключа конечно. | прямого сравнения ключей и
| их упорядоченностью.
| Quicksort, Heapsort...
Для сортировок сравнениями давно доказана теорема
о максимальном быстродействии: O( nlogn ).
Для сортировок распределением это - O(n). Быстрее сортировать нельзя.
Итак, наибыстрейшие сортировки -
Quicksort - быстрая, для больших массивов
InsertSort - для массивов <20 элементов, списков
Radix sort - распределяющая
и молодой гибрид быстрой/распределяющей:
Multiway Quicksort /MQS / - быстрая с составными ключами.
Полезна, например, для больших массивов строк.
В конкретном случае надо смотреть по данным и имеющимся в наличии ресурсам,
однако в типичных случаях наибыстрейшими решениями станут <см выше>.
===========================================================================
> 8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка
> ?
===========================================================================
A: Kantor Ilia
К сожалению, или к счастью, единица информации в современной технике
способна применять лишь 2 значения: 1 и 0.
А значит, любые компьютерные данные тоже могут принимать ограниченное
количество значений, так как состоят из некоторого числа битов ;-)).
Пусть имеем максимум по k байт в каждом ключе ( хотя за элемент
сортировки вполне можно принять и что-либо другое, например слово -
двойной байт, или буквы, если сортируются строки). k должно быть
известно заранее, до сортировки.
Разрядность данных ( количество возможных значений элементов k) - m.
Если мы сортируем слова, то элемент сортировки - буква. m = 33.
Если в самом длинном слове 10 букв, k = 10.
Обычно мы будем сортировать данные по ключам из k байт, m=256.
----------------------------------------------------------------------
Пусть у нас есть массив source из n элементов по одному байту в каждом.
Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 },
и проделать с ним все операции, имея в виду m=9.
I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и
заполняться она будет так:
for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;
Для нашего примера будем иметь distr = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 },
то есть i-ый элемент distr[] - количество ключей со значением i.
Заполним таблицу индексов:
int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];
В index[i] мы поместили информацию о будущем количестве символов в
отсортированном массиве до символа с ключом i.
Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.
А теперь заполняем новосозданный массив sorted размера n:
for ( i = 0; i < n ; i++ )
{
sorted[ index[ source[i] ] ]=source[i];
// попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
index[ source[i] ] = index[ source[i] ] +1;
}
Итак, мы научились за O ( n ) сортировать байты. А от байтов до строк
и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.
Будем действовать в десятичной системе и сортировать обычные числа
( m = 10 ).
сначала они в сортируем по младшему на один
беспорядке: разряду: выше: и еще раз:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554
Hу вот мы и отсортировали за O ( k*n ) шагов. Если количество
возможных различных ключей ненамного превышает общее их число, то
поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой
сортировки' !
Реализация на C++ для long int'ов. Сам не делал - валялась в и-нете.
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
void radix (int byte, long N, long *source, long *dest)
{
long count[256];
long index[256];
memset (count, 0, sizeof (count));
for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
index[0]=0;
for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
for(i=0;i<N;i++) dest[index[((source[i])>>(byte*8))&0xff]++]=source[i];
}
void radixsort (long *source, long *temp, long N)
{
radix (0, N, source, temp);
radix (1, N, temp, source);
radix (2, N, source, temp);
radix (3, N, temp, source);
}
void make_random (long *data, long N)
{
for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
}
long data[10000];
long temp[10000];
void main (void)
{
make_random(data, 10000);
radixsort (data, temp, 10000);
for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
}
===========================================================================
> 9. Что быстрее: распределяющая сортировка или QuickSort ?
===========================================================================
A: Kantor Ilia
Когда количество возможных различных ключей ненамного больше их общего
числа - распределяющая.
Различных ключей очень много, размер массива сравнительно небольшой
- быстрая.
===========================================================================
> 10. Есть большой файл. Как его отсортировать ?
===========================================================================
A: Tomas Niemann
Многофазная сортировка
Этот тип сортировки относится к так называемым 'сортировкам слиянием'.
Слиянием называется процесс объединения нескольких упорядоченных серий в
одну.
Пример для 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
Каждый pаз мы беpем свеpху наименьший элемент.
Таким образом, каждая операция слияния серий требует n пересылок
элементов, где n - общее число элементов серий.
Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем
слиять элементы со входных лент на выходную, пока какая-либо из них не
опустеет. Затем она станет входной.
Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии
обозначены буквами fi, в таблице - количество элементов.
Тип f1 f2 f3 f4 f5 f6
16 15 14 12 8
8 7 6 4 0 8
4 3 2 0 4 4
2 1 0 2 2 2
1 0 1 1 1 1
0 1 0 0 0 0
В каждый момент времени слияние происходит на пустую ленту с остальных,
поэтому число требующихся проходов приблизительно равно log N n. В данном
примере распределение начальных серий побрано искусственно. Для идеальной
сортировки исходные числа серий должны быть суммами n - 1 , n - 2 , ... , 1
последовательных чисел Фибоначчи порядка n - 2.
Число Фибоначчи порядка p определяются следующим образом:
fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p,
fp(p) = 1,
fi(p) = 0 для 0 <= i < p.
Очевидно, обычные числа Фибоначчи имеют порядок 1.
Поэтому предположим существование фиктивных серий, таких что сумма
фиктивных с реальными дает идеальное число.
Сначала все данные располагаются на одной ленте. Лента читается и
отрезки распределяются по другим лентам, имеющимся в системе. после того,
как созданы начальные отрезки, они сливаются, как описано выше. Один из
методов, который можно использовать для создания начальных отрезков, состоит
в чтении порции записей в память, их сортировке и записи результата на
ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот
алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала
мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут
исчерпаны входные данные:
* Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >=
значения ключа последней прочитанной записи.
* Если все "старые" ключи меньше последнего ключа, то мы достигли конца
отрезка. Выбираем запись с наименьшим ключом в качестве первого
элемента следующего отрезка.
* Записываем выбранную запись.
* Заменяем выбранную и записанную запись на новую из входного файла.
Hа следующей таблице выбор с замещением иллюстрируются для совсем
маленького файла.
Hачало файла - справа. Чтобы упростить пример, считается, что в буфер
помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер
помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в
выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась
запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла -
с ключом 4. Процесс продолжается до шага F, где мы оказывается, что
последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы
заканчиваем формирование текущего отрезка и начинаем формирование
следующего.
Шаг Вход Буфер Выход
A 5-3-4-8-6-7
B 5-3-4-8 6-7
C 5-3-4 8-7 6
D 5-3 8-4 7-6
E 5 3-4 8-7-6
F 5-4 3 | 8-7-6
G 5 4-3 | 8-7-6
H 5-4-3 | 8-7-6
Обратите внимание мы храним записи в буфере до тех пор, пока не
наступит время записать их в выходной файл. Если вход случаен, средняя длина
отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть
как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот
метод, вообще говоря, более эффективен промежуточных, частичных сортировок.
Прочитав из входног === Cut ===
/\/ Искренне ваш, Илья \/\
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
<без заголовка> |
Ilia Kantor |
10 Jan 2002 22:51:18 |
|
|
