|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 17 Jan 2002 02:38:32
To : All
Subject : S0rting FAQ 2.0 многое добавлено, многое пеpеписано
--------------------------------------------------------------------------------
Публикую по пpосьбам
=== Cut ===
S0rting FAQ v2.0c
FAQ по СОРТИРОВКАМ версия от 18.01.2002
> Вопросы
1. Ликбез для понимания важной информации:
Что означает символ O(n) ? Оценки Omega() и Theta()
Почему _не пишется_ основание логарифма: O(logn) ?
2. Какие на сегодняшний день самые эффективные методы сортировки ?
3. Описание SelectSort (сортировка выбором).
4. Описание и исходник InsertSort (сортировка простыми вставками).
5. Описание и исходник ShellSort (сортировка Шелла).
6. Описание и исходник QuickSort (быстрая сортировка).
7. Описание и исходник HeapSort (пирамидальная сортировка).
8. Описание и исходник MergeSort (сортировка слиянием)*
* Under construction
9. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?
10. Требования и свойства сортировок. Что когда лучше?
10.1 Какая самая быстрая сортировка ?
10.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?
11. Есть большой файл. Как его отсортировать ? Сортировка слиянием.
> Ответы
====================================================================
> 1. Ликбез для понимания важной информации: Что означает символ O(n) ?
> Почему _не пишется_ основание логарифма: O ( log n ) ?
====================================================================
Оценки времени исполнения. 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
Hо 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() - точная оценка асимптотики.
Это множество 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
Вертикальной чертой отмечена граница уже отсортированной части
массива.
====================================================================
> 4. Сортировка простыми вставками.
====================================================================
Алгоритм
Все элементы условно разделяются на готовую
последовательность a1 ... ai-1 и входную ai ... an. Hа
каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й
элемент входной последовательности и вставляем его на
нужное место в готовую.
Пример:
Hачальные ключи 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. Hайден 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
Пример на Си - 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;
}
}
====================================================================
> 5. Описание и исходник 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 );
}
====================================================================
> 6. Описание и исходник QuickSort (быстрая сортировка)
====================================================================
Основной алгоритм
Выберем случайным образом какой-то элемент х и
просмотрим массив, двигаясь слева направо, пока не
найдем аi больший x, а затем справа налево, пока не
найдем аi меньший х. Поменяем их местами и продолжим
процесс просмотра с обменом, пока просмотры не
встретятся где-то в середине массива.
В результате массив разделится на две части:
левую - с ключами, меньшими х и правую - с ключами,
большими х.
Этот шаг называется разделением. Х - центром.
К получившимся частям рекурсивно применяем ту же
процедуру.
В результате получается очень эффективная сортировка
Пример рекурсивной 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 средний из первого, последнего и среднего
элементов. В этом случае среднее число проходов на случайных
данных уменьшится в 7/6 раз.
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;
}
}
}
}
====================================================================
> 7. Описание и исходник HeapSort (пирамидальная сортировка).
====================================================================
Рассмотрим слегка модифицированную сортировку выбором:
A[1..N] - сортируемый массив из n элементов.
for ( i=N; i>1; i--)
айти наибольший из элементов 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
=== Cut ===
ъщю До следующих встреч, All ющъ
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
S0rting FAQ 2.0 многое добавлено, многое пеpеписано |
Ilia Kantor |
17 Jan 2002 02:38:32 |
|
|
