might this help ? S0rting FAQ 1/4
- From
- Ilia Kantor (2:5020/1815.6)
- To
- All
- Date
- 2002-05-01T22:27:22Z
- Area
- RU.ALGORITHMS
Соpтиpовка слов идет последним вопpосом.
=== Cut ===
S0rting FAQ v2.3
FAQ по СОРТИРОВКАМ версия от 21.03.2002
В процессе работы над FAQом я смотрел многие источники
по этим вопросам, в которых (даже написанных самыми уважаемыми
авторами) иногда давались разные, противоречивые сведения.
Особенно это касается характеристик сортировок.
Однако 'субъективных' оценок алгоритмов не бывает, поэтому по
всем вопросам, вызывающим _аргументированные_ сомнения, пишите.
Ilia Kantor
web: http://algolist.da.ru
email: <algolist@mail.ru>
Fido: 2:5020/1815.6@FidoNet
> Вопросы
1. Ликбез для понимания важной информации:
Что означает символ O(n) ? Оценки Omega() и Theta()
Почему _не пишется_ основание логарифма: O(logn) ?
2. Какие на сегодняшний день самые эффективные методы сортировки ?
3. Описание и исходник SelectSort (сортировка выбором).
4. Сортировка пузырьком BubbleSort и ее улучшения с исходниками.
5. Описание и исходник InsertSort (сортировка простыми вставками).
6. Описание и исходник ShellSort (сортировка Шелла).
7. Описание и исходник сортировки двоичным деревом
(TreeSort, 'древесная сортировка'). Выбор с замещением.
8. Описание и исходник QuickSort (быстрая сортировка).
9. Описание и исходник HeapSort (пирамидальная сортировка).
10. Описание MergeSort (сортировка слиянием).
11. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?
12. Требования и свойства сортировок. Что когда лучше?
12.1 Какая самая быстрая сортировка ?
12.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?
13. Есть большой файл. Как его отсортировать ? Многофазное слияние.
14. Есть большое количество слов. Как их отсортировать ?
App. Использованная литература.
> Ответы
====================================================================
> 1. Ликбез для понимания важной информации:
> Что означает символ O(n) ? Оценки Omega() и Theta()
> Почему _не пишется_ основание логарифма: O(logn) ?
====================================================================
Оценки времени исполнения. Cимвол O().
Для оценки производительности алгоритмов можно использовать
разные подходы. Самый бесхитростный - просто запустить каждый
алгоритм на нескольких задачах и сравнить время исполнения. Другой
способ - оценить время исполнения через символ O(n) (читается так:
о большое от n). n здесь - обычно количество обрабатываемых элементов
данных (например, сортируемых чисел).
Также такую оценку называют 'асимптотикой', так как она обозначает
асимптотическое поведение алгоритма ( n -> беск. )
Когда используют обозначение O(), имеют в виду не точное время
исполнения, а только его предел сверху, причем с точностью до
постоянного множителя. Когда говорят, например, что алгоритму
требуется время порядка O(n^2), имеют в виду, что время исполнения
задачи растет не быстрее, чем квадрат количества элементов. Чтобы
почувствовать, что это такое, посмотрите на таблицу, где приведены
числа, иллюстрирующие скорость роста для нескольких разных функций.
n log n n*log n n^2
1 0 0 1
16 4 64 256
256 8 2,048 65,536
4,096 12 49,152 16,777,216
65,536 16 1,048,565 4,294,967,296
1,048,476 20 20,969,520 1,099,301,922,576
16,775,616 24 402,614,784 281,421,292,179,456
Если считать, что числа в таблице соответствуют микросекундам,
то для задачи с 1048476 элементами алгоритму с временем работы
O(log n) потребуется 20 микросекунд, а алгоритму с временем работы
O(n^2) - более 12 дней.
> Если оба алгоритма, например, O ( n*log n ), то это отнюдь
> не значит, что они одинаково эффективны.
Символ О не учитывает константу, то есть первый может быть, скажем
в 1000 раз эффективнее. Это значит лишь то, что время (или требуемая
память или что-либо еще, что надо оценить) возрастает приблизительно
c такой же скоростью, как функция n*log n.
> За функцию берется количество операций, возрастающее быстрее всего.
То есть, если в программе одна функция выполняется O(n) раз -
например, умножение, а сложение - O(n^2) раз, то общая сложность -
O(n^2), так как n^2 возрастает быстрее.
Практический смысл этого в нашем случае такой: при увеличении n
более быстрые ( в определенное, константное число раз ) сложения
станут выполнятся настолько часто, что будут влиять на производительность
много сильнее, нежели медленные, но редкие умножения.
> Основание логарифма не пишется.
Причина этого весьма проста. Пусть у нас есть
O( log n ). Перейдем к основанию 3: log n = log n / log 2.
2 2 3 3
Но 1/log 2, как и любую константу, асимптотика - символ O()
3
не учитывает. Таким образом, O(log n) = O(log n).
2 3
К любому основанию мы можем перейти аналогично, а, значит, и писать
его не имеет смысла.
В заключение, привожу формальную трактовку обозначения O(g(n)) для
положительных функций f(n), g(n):
Опp.1 O(g(n)) - множество функций f(n), для котоpых существуют
положительные константы c, n0, такие что
f(n) <= c*g(n) для всех n>=n0
Опp.2 Запись f(n) = O(g(n)) означает, что f(n) - элемент множества
O(g(n))
Иногда символ O() используют в более широком смысле, подразумевая не
только верхнюю, но и нижнюю оценку Theta(): существуют c1, c2, n0 > 0:
0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0
Кроме символа O() используются также оценки
Omega(g(n)) - нижняя оценка: множество f(n): существуют c, n0>0:
c*g(n) <= f(n)
Theta(g(n)) - комбинация O() и Omega(): точная оценка асимптотики.
Theta(g(n) - множество f(n): существуют c1, c2, n0>0:
0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0
Все описанные свойства оценки O() также верны для Omega() и Theta().
Интуитивный смысл оценок:
f = O(g) - f растет не быстрее g }
f = Omega(g) - f растет не медленнее g } при n->00
f = Theta(g) - f растет так же, как g }
====================================================================
> 2. Какие на сегодняшний день самые эффективные методы сортировки ?
====================================================================
Быстрая сортировка, распределяющая сортировка и соpтиpовка слиянием.
Для прикладных задач, использующих элементы сортировки, также
очень полезна пирамидальная сортировка.
Сpавнительные хаpактеpистики методов более подробно
описаны в соответствующем вопpосе.
====================================================================
> 3. Сортировка выбором.
====================================================================
A[1..N] - сортируемый массив из n элементов.
for ( i=1; i<N; i++)
Найти наименьший из элементов i..N и поменять его местами с i-м.
Пример действий для случайного массива A[1..8]
44 55 12 42 94 18 06 67 исходный массив
i=1 06| 55 12 42 94 18 44 67 06 <-> 44
i=2 06 12| 55 42 94 18 44 67 12 <-> 55
i=3 06 12 18| 42 94 55 44 67 18 <-> 55
i=4 06 12 18 42| 94 55 44 67 42 <-> 42
i=5 06 12 18 42 44| 55 94 67 44 <-> 94
i=6 06 12 18 42 44 55| 94 67 55 <-> 55
i=7 06 12 18 42 44 55 67| 94 67 <-> 94
Вертикальной чертой отмечена граница уже отсортированной части
массива.
Сортировка выбором - простейший алгоритм, на практике не
используемый ввиду низкого быстродействия. Вместо этого
применяют ее улучшение - пирамидальную сортировку (Heapsort),
описанную в другом вопросе, а также (иногда) 'древесную сортировку'
(TreeSort).
Пример на Паскале - Николас Вирт.
--------------------------------------------------------------------
{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure SelectSort;
var i, j, k: index; x:item;
begin for i:=1 to n-1 do
begin k:=i; x:=a[i];
for j:=i+1 to n do
if a[j].key < x.key then
begin k:=j; x:=a[j];
end;
a[k]:=a[i]; a[i]:=x;
end;
end;
====================================================================
> 4. Сортировка пузырьком(BubbleSort) и ее улучшения.
====================================================================
Операция сравнения/перестановки выполняется для каждых двух стоящих
рядом элементов. После первого прохода по массиву "вверху" оказывается
самый "легкий" элемент. Следующий цикл сортировки выполняется начиная
со второго элемента, в результате чего вторым в массиве оказывается
второй наименьший по величине элемент, и так далее.
{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure BubbleSort;
var i,j: index; x:item;
begin for i:=2 to n do
begin for j:=n downto i do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
end;
end;
end;
Пример 1. Проходим по массиву снизу вверх. Меньшие/более легкие/
элементы 'всплывают' наверх, давая название методу.
Начальные i i i i i i i
ключи 2 3 4 5 6 7 8
44 /-> 06 06 06 06 06 06 06
55 | 44 /-> 12 12 12 12 12 12
12 | 55 | 44 /-> 18 18 18 18 18
42 | 12-/ 55 | 44 /-> 42 42 42 42
94 | 42 /-> 18-/ 55 | 44 --> 44 44 44
18 | 94 | 42 42-/ 55 55 --> 55 55
06-/ 18-/ 94 -> 67 67 67 67 --> 67
67 67 67-/ 94 94 94 94 94
Алгоритм пузырька очень медленен и неэффективен. Тем не менее,
у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.
Посмотрите на пример 1. Три последних прохода никак не влияют на
порядок элементов, поскольку те уже отсортированы. Очевидный способ улучшить
алгоритм - запоминать, производился ли на данном проходе какой-либо обмен.
Если нет - это означает, что алгоритм может закончить работу.
Этот процесс улучшения можно продолжить, если запоминать не столько
сам файт обмена, но и место (индекс) последнего обмена. Ведь ясно, что
все пары соседих элементов с индексами, меньшими этого индекса k,
уже расположены в нужном порядке. Поэтому следующие прозоды можно заканчивать
на этом индексе, вместо того чтобы двигаться до установленной заранее
нижней границы i.
Пойдем дальше: внимательный человек легко может заметить странную
асимметрию: один неправильно расположенный 'пузырек' в 'тяжелом'
конце рассортированного массива всплывет за один проход, а неправильно
расположенный элемент в легком конце будет опускаться на правильное
место только на один шаг при каждом проходе.
Например, массив 12 18 42 44 55 67 94 06 будет отсортирован за 1 проход,
а сортировка массива 94 06 12 18 42 44 55 67 потребует 7 проходов.
Эта неестественная асимметрия подсказывает третье улучшение:
менять направление следующих один за другим проходов.
Получившийся алгоритм иногда называют 'шейкер-сортировкой'.
Пример его работы на том же входном массиве.
l = 2 3 3 4 4
r = 8 8 7 7 4
44 /-> 06 06 06 06
55 | 44 44 /-> 12 12
12 | 55 -\ 12 -/ 44 -\ 18
42 | 12 | 42 /-> 18 | 42
94 | 42 \-> 55 | 42 \-> 44
18 | 94 -\ 18 -/ 55 55
06 -/ 18 | 67 67 67
67 67 \-> 94 94 94
Проходы: /|\ | /|\ | /|\
| \|/ | \|/ |
procedure ShakerSort;
var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
repeat
for j:=r downto l do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
l:=k+1;
for j:=l to r do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
r:=k-1;
until l>r;
end;
Анализ алгоритма простого пузырька:
Число сравнений
C = 1/2 (n^2 - n),
Числа пересылок:
Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).
Анализ шейкер-сортировки (из книги Д.Кнута):
Минимальное число сравнений Cmin = n-1
Среднее число проходов пропорционально n - k1*корень(n),
Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
Но, как видно, все предложенные усовершенствования не влияют на число
обменов. К сожалению, обмен - операция, как правило, гораздо более
медленная, чем сравнение ключей, поэтому реальный эффект улучшений
гораздо меньше, чем можно было бы ожидать.
Метод пузырька и описанные улучшения на практике крайне неэффективны,
SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
использовать, когда известно, что элементы уже почти упорядочены.
Но даже в этом случае обычно применяют все же InsertSort, которая
менее чувствительна к степени упорядоченности.
====================================================================
> 5. Сортировка простыми вставками.
====================================================================
Алгоритм
Все элементы условно разделяются на готовую
последовательность a1 ... ai-1 и входную ai ... an. На
каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й
элемент входной последовательности и вставляем его на
нужное место в готовую.
Пример:
Начальные ключи 44 \\ 55 12 42 94 18 06 67
i = 2 44 55 \\ 12 42 94 18 06 67
i = 3 12 44 55 \\ 42 94 18 06 67
i = 4 12 42 44 55 \\ 94 18 06 67
i = 5 12 42 44 55 94 \\ 18 06 67
i = 6 12 18 42 44 55 94 \\ 06 67
i = 7 06 12 18 42 44 55 94 \\ 67
i = 8 06 12 18 42 44 55 67 94 \\
При поиске подходящего места удобно 'просеивать' x,
сравнивая его с очередным элементом ai и либо вставляя его,
либо пересылая ai направо и продвигаясь налево.
Просеивание может кончиться при двух условиях:
1. Найден ai с ключом, меньшим x.
2. Достигнут конец готовой последовательности.
Метод хорош устойчивостью сортировки, удобством для
реализации в списках и, самое главное, естественностью
поведения. То есть уже частично отсортированный массив
будут досортирован им гораздо быстрее чем многими
'продвинутыми' методами.
Анализ
Число сравнений
минимальное: n - 1
среднее: ( n^2 + n - 2 ) / 4
максимальное: ( n^2 + n ) * / 2 - 1
Количество пересылок
минимальное: 2 * ( n - 1 )
среднее: ( n^2 + 9 * n - 10 ) / 4
максимальное: ( n^2 + 3 * n - 4 ) / 2
Примечания.
1. Если мы работаем с массивом, а не списком, то искать место вставки
очередного ai в готовую последовательность можно бинарным поиском,
ведь a1..a_i-1 уже отсортированы!
При этом количество сравнений снизится до O(nlogn),
но сортировка станет вести себя крайне неестественно (уже
отсортированный массив обрабатывается дольше всего), а,
самое главное, количество пересылок по-прежнему останется O(n^2).
2. При работе с массивами можно использовать и другое улучшение
InsertSort'a - ShellSort (описана в другом вопросе).
Пример на Си - Tomas Niemann.
--------------------------------------------------------------------
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */
#define compGT(a,b) (a > b) /* Функция сравнения */
void insertSort(T *a, tblIndex lb, tblIndex ub) {
item t;
tblIndex i, j;
/***********************
* сортируем a[lb..ub] *
***********************/
for (i = lb + 1; i <= ub; i++) {
t = a[i];
/* Сдвигаем элементы вниз, пока */
/* не найдем место вставки. */
for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] = a[j];
/* вставка */
a[j+1] = t;
}
}
====================================================================
> 6. Описание и исходник ShellSort (сортировка Шелла)
====================================================================
Этот алгоритм - модификация сортировки простыми вставками.
Идея, например, в случае 16 чисел n1 ... n16 такова:
Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов
(n1, n9), (n2, n10), ... , (n8, n16).
Потом сортируем каждую из четырех групп по 4 элемента (n1, n5, n9, n13),
..., (n4, n8, n12, n16). Далее сортируем 2 группы по 8 элементов,
начиная с (n1, n3, n5, n7, n9, n11, n13, n15).
А в конце сортируем вставками все 16 элементов.
Очевидно, лишь последняя сортировка необходима,
чтобы расположить все элементы по своим местам.
Так зачем нужны остальные ?
На самом деле они продвигают элементы максимально близко
к соответствующим позициям, так что в последней стадии число
перемещений будет весьма невелико. Они и так почти рассортированы.
Были проведены многочисленные исследования по вопросу,
какова должна быть последовательность расстояний между сортируемыми
элементами в зависимости от прохода (инкремент).
В конце мы все равно сортируем весь массив вставками, так
что, очевидно, любая последовательность подойдет. Набор
..., 8, 4, 2, 1 - неплохой выбор, особенно,
когда N - степень двойки. Но гораздо лучше будет взять
( 3k - 1 )/2, ..., 40, 13, 4, 1
Ее можно вычислить рекуррентно:
i_1 = 1, i_k+1 = 3i_k + 1, k = 1, 2, ...
При этой последовательности количество операций даже
в наихудшем случае - порядка N^3/2.
Для случайной последовательности при N < 60000
количество операций, приблизительно, N^1.25,
однако уже при N > 50 QuickSort быстрее.
Исходник на Си.
void shell(unsigned long n, float a[])
{
unsigned long i, j, inc;
float v;
inc=1; // начальный инкремент
do {
inc *=3;
inc++;
} while (inc <= n);
do { // Цикл частичных сортировок
inc /=3;
// Внутренний цикл простых вставок
for (i=inc+1; i<=n; i++) {
v=a[i];
j=i;
while ( a[j-inc] > v) {
a[j] = a[j-inc];
j -= inc;
if ( j <= inc ) break;
}
a[j]=v;
}
} while ( inc > 1 );
}
====================================================================
> 7. Сортировка двоичным деревом, 'древесная сортировка'.
====================================================================
Двоичным(бинарным) деревом назовем упорядоченную структуру данных,
в которой каждому элементу - предшественнику или корню (под)дерева -
поставлены в соответствие по крайней мере два других элемента (преемника).
Причем для каждого предшественника выполнено следующее правило:
левый преемник всегда меньше, а правый преемник всегда больше или равен
предшественнику.
Вместо 'предшественник' и 'преемник' также употребляют термины
'родитель' и 'сын'. Все элементы дерева также называют 'узлами'.
При добавлении в дерево нового элемента его последовательно сравнивают
с нижестоящими узлами, таким образом вставляя на место.
Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
и так далее, пока есть сыновья, с которыми можно сравнить.
Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:
44 44 44 44 44
\ / \ / \ / \
55 12 55 12 55 12 55
\ \ \
42 42 94
(**) 44 44 (*) 44
/ \ / \ / \
12 55 12 55 12 55
\ \ / \ \ / \ \
42 94 06 42 94 06 42 94
/ / / /
18 18 18 67
Дерево может быть и более-менее ровным, как на (*), может и иметь всего
две основные ветви (**), а если входная последовательность уже отсортирована,
то дерево выродится в линейный список.
Если мы будем рекурсивно обходить дерево по правилу
"левый сын - родитель - правый сын", то, записывая все
встречающиеся элементы в массив, мы получим упорядоченное
в порядке возрастания множество. На этом и основана идея сортировки деревом.
Более подробно правило обхода можно сформулировать как
обойти левое поддерево - вывести корень - обойти правое поддерево,
где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается
с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.
/*********** сортировка с помощью двоичного дерева *************/
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
int a; // данные
struct tree *left; // левый сын
struct tree *right; // правый сын
} TREE;
TREE *add_to_tree(TREE *root, int new_value)
{
if (root==NULL) // если нет сыновей - создаем новый элемент
{
root = (TREE*)malloc(sizeof(TREE));
root->a = new_value;
root->left = root->right = 0;
return root;
}
if (root->a < new_value) // добавлем ветвь
root->right = add_to_tree(root->right, new_value);
else
root->left = add_to_tree(root->left, new_value);
return root;
}
=== Cut ===
·∙■ До следующих встреч, All ■∙·
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)