|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 10 Jan 2002 22:51:44
To : All
Subject : S0rting FAQ 1.2 (Some fixes and additions)
--------------------------------------------------------------------------------
Я тут добавил кой-чего в конец 1 вопpоса и в описание Quicksort.
Плюс есть немного мелких испpавлений.
Кстати, люди жалуются, что описание пиpамидальной соpтиpовки можно понять
только если pаньше знал - и то с тpудом.
Что там попpавить/добавить, чтобы стало понятно всем ?
Кто-нибудь компилял исходник последнего вопpоса? Есть те, у кого оно
компилится, но не пашет или pаботает непpавильно?
=== Cut ===
Sorting FAQ V1.2
FAQ по СОРТИРОВКАМ версия от 8.01.2002
> Вопросы
1. Ликбез для понимания важной информации: Что означает символ O(n) ?
Почему _не пишется_ основание логарифма: O ( log n ) ?
2. Какие на сегодняшний день самые эффективные методы сортировки ?
3. Описание и исходник InsertSort (сортировка простыми вставками).
4. Описание и исходник QuickSort (быстрая сортировка).
5. Описание и исходник HeapSort (пирамидальная сортировка).
6. Требования QuickSort и HeapSort. InsertSort... Что лучше ?
7. Какая самая быстрая сортировка ?
8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?
9. Что лучше: распределяющая сортировка или быстрая ?
10. Есть большой файл. Как его отсортировать ? Сортировка слиянием.
> Ответы
====================================================================
> 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)),
используемую в литературе по алгоритмам:
Опp.1 O(g(n)) - множество функций f(n), для котоpых существуют
положительные константы c1, c2 и n0, такие что
0 <= c1*g(n) <= f(n) <= c2*g(n) для всех n >= n0
Опp.2 Запись f(n) = O(g(n)) означает, что f(n) - элемент множества
O(g(n))
Обращаю Ваше внимание на то, что в математической литературе
символ O() имеет другой смысл, обозначая лишь верхюю оценку.
При этом оределению, данному выше, соответствует символ Тэта().
====================================================================
> 2. Какие на сегодняшний день самые эффективные методы сортировки ?
====================================================================
A: Kantor Ilia
быстрая сортировка, распределяющая сортировка и быстрая сортировка
с составными ключами, которая в FAQ не входит.
Для прикладных задач, использующих элементы сортировки, также
очень полезна пирамидальная сортировка.
====================================================================
> 3. Сортировка простыми вставками.
====================================================================
A: Nicolas Virt - Tomas Niemann ;-))
Алгоритм
Все элементы условно разделяются на готовую
последовательность 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;
}
}
====================================================================
> 4. Описание и исходник 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;
}
}
}
}
====================================================================
> 5. Описание и исходник HeapSort (пирамидальная сортировка).
====================================================================
A: Nicolas Virt
Hазовем пирамидой последовательность элементов
h_l , h_l+1 , ... , h_r
такую, что
h_i <= h_2i
h_i <= h_2i+1
для всякого i = l , ... , r/2
Геометрическая интерпретация пирамиды:
h1
/ \
=== Cut ===
Здесь был я. [Team Гитара][Team MUD][Team Chinese][Team NLP]
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
