|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 28 Mar 2002 22:13:30
To : All
Subject : Sfaq 3/4
--------------------------------------------------------------------------------
=== Cut ===
3. Полученной последовательности присваивается имя а, и
повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются
в упорядученные четверки.
4. Предыдущие шаги повторяются: четверки сливаются в восьмерки, и весь
процесс продолжается до тех пор, пока не будет упорядочена вся
последовательность, ведь длины сливаемых последовательностей каждый
раз удваиваются.
Пример: последовательность 44 55 12 42 94 18 06 67
Hа первом шаге разбиение дает последовательности
44 55 12 42
94 18 06 67
Слияние отдельных компонент (которые являются упорядоченными
последовательностями длины 1) в упорядоченные пары дает:
44 94 ' 18 55 ' 06 12 ' 42 67
Hовое разбиение и слияние упорядоченных пар дает:
06 12 44 94 ' 18 42 55 67
Третье разбиение и слияние приводят к нужному результату:
06 12 18 42 44 55 67 94.
Операция, которая однократно обрабатывает все множество данных,
называется 'фазой', а наименьший процесс, который, повторяясь,
образует процесс сортировки, называется 'проходом' или 'этапом'.
В приведенном выше примере сортировка производится за три прохода,
каждый проход состоит из фазы разбиения и фазы слияния.
Для выполнения сортировки требуются три списка(ленты, файла),
поэтому процесс называется трехпутевым(трехленточным) слиянием.
Hа этом же принципе основаны и другие, более сложные и эффективные
сортировки слиянием, как-то: естественное слияние, многопутевое
сбалансированное слияние, каскадная и многофазная сортировки.
Для получения более подробной информации рекомундую почитать
H.Вирт "Алгоритмы + Структуры данных = Программы".
- однофазное/сбалансированное слияние (4-путевое)
- естественное слияние
- сбалансированное многопутевое слияние ( N/2-путевое )
- многофазная сортировка слиянием ( N-1-путевое слияние )
Д.Кнут "Искуссво программирования на ЭВМ"
асколько помню - приблизительно то же, гораздо хуже описана многофазная
сортировка, зато есть
- каскадная сортировка слиянием
- осциллирующая сортировка слиянием(малоприменима)
Многофазная сортировка слиянием будет описана в вопросе
о сортировке файлов. Там же будет дан ее исходник.
а практике она имеет приблизительно ту же эффективность, что
и каскадная сортировка слиянием - наилучшую для данного класса методов.
===========================================================================
> 11. Что такое Байтовая, Цифровая, Радиксная или Распределяющая
> сортировка ?
===========================================================================
A: Kantor Ilia
Пусть имеем максимум по k байт в каждом ключе ( хотя за элемент
сортировки вполне можно принять и что-либо другое, например слово -
двойной байт, или буквы, если сортируются строки). k должно быть
известно заранее, до сортировки.
Разрядность данных ( количество возможных значений элементов ) - m,
также должна быть известна заранее и постоянна.
Если мы сортируем слова, то элемент сортировки - буква. m = 33.
Если в самом длинном слове 10 букв, k = 10.
Обычно мы будем сортировать данные по ключам из k байт, m=256.
----------------------------------------------------------------------
Пусть у нас есть массив source из n элементов по одному байту в каждом.
Для примера можете выписать на листочек массив
source[1..7] = { 7,9,8,5,4,7,7 }, и проделать с ним все операции,
имея в виду m=9. n здесь, очевидно, равно 7.
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
/|\ /|\ /|\
| | |
Вот мы и отсортировали массив за O(kn) шагов. Если количество
возможных различных ключей ненамного превышает общее их число, то
поразрядная сортировка оказывается гораздо быстрее даже 'быстрой
сортировки' !
Распределяющая сортировка, требует O(n) дополнительной памяти.
Пример(учебный) реализации radixsort на Си++ для long int'ов.
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
void radix (int byte, long N, long *source, long *dest)
{
// *source - входной массив,
// *dest - отсортированный.
long count[256]; // вообще говоря, можно обойтись
long index[256]; // одним массивом count[]
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)
{
// Сортируем по всем 4 разрядам
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';
}
Примечания.
1. К сожалению, или к счастью, единица информации в современной
технике способна принимать лишь 2 значения: 1 и 0.
А значит, любые компьютерные данные тоже могут принимать
ограниченное количество значений, так как состоят из некоторого
числа битов ;-)).
Таким образом, распределяющая сортировка потенциально применима
где угодно. Другое дело, что если разрядность данных большая
по сравнению с общим количеством элементов, то скорость работы
оставит желать много лучшего.
2. Алгоритм, описанный выше, очевидно, требует O(n) памяти.
Существует похожий алгоритм, использующий лишь O(logn).
Модифицированная Radix Sort:
Будем сортировать по каждой позиции символа 'на месте', начиная справа:
сначала сортируем по первой позиции, затем к каждой части массива,
относящейся к одному и тому же значению, рекурсивно
применяем ту же процедуру и т.д.
Этот вариант называется 'Radix exchange sort' и
представляет собой скорее разновидность QuickSort.
Hа мой взгляд, она объединяет больше плохих черт обоих методов,
нежели хороших, но вполне может пригодиться в какой-то ситуации.
> Существует вариант распределяющей сортировки для списков,
> каждый элемент которых принимает конечное множество значений.
> Он даже проще в реализации, понимании и использовании.
Предположим, что элементы линейного списка В есть Т-разрядные
положительные десятичные числа D(j,n) - j-я справа цифра в десятичном
числе n>=0, т.е. D(j,n)=floor(n/m)%10, где m=10^(j-1).
(floor - округление в меньшую сторону)
Пусть В0,В1,...,В9 - вспомогательные списки (карманы), вначале пустые.
Для реализации распределяющей сортировки выполняется процедура,
состоящая из двух процессов, называемых распределение и сборка
для j=1,2,...,T.
PАСПРЕДЕЛЕHИЕ
заключается в том, что элемент Кi (i=1,N) из В добавляется как
последний в список Bm, где m=D(j,Ki), и таким образом получаем
десять списков, в каждом из которых j-тые разряды чисел одинаковы и
равны m.
СБОРКА
объединяет списки В0,В1,...,В9 в этом же порядке,
образуя один список В.
> Число карманов - количество возможных значений элемента списка.
Исходный список можно сделать односвязный, а сортировку организовать так,
чтобы для карманов В0,В1,...,В9 не использовать дополнительной памяти, т.е
элементы списка не перемещать, а с помощью перестановки указателей
присоединять их к тому или иному карману.
В представленной ниже программе функция pocket реализует распределяющую
сортировку связанного линейного списка (указатель q), в котором содержатся
Т-разрядные десятичные положительные числа, без использования
дополнительной памяти;
в функции a[i], b[i] указывают соответственно на первый и на последний
элементы кармана Bi.
/* распределяющая сортировка списка */
#include <stdlib.h>
#include <stdio.h>
typedef struct SP1_ {
long val;
struct SP1_ *next;
} SP1;
/* функция сортировки возвращает указатель на начало
отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* t - разрядность (максимальная длина числа) */
int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++) {
for(i=0;i<=9;i++) a[i]=(b[i]=NULL);
while(q!=NULL) {
k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q; else r->next=q;
r=b[k]=q;
q=q->next;
r->next=NULL;
}
for(i=0;i<=9;i++) if (a[i]!=NULL) break;
q=a[i];
r=b[i];
for(k=i+1;k<=9;k++)
if(a[k]!=NULL) {
r->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
SP1 *q, *r;
/* Это будем сортировать */
long a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
q=(SP1 *)malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<14;i++) { /* формирование списка */
r->next=(SP1 *)malloc(sizeof(SP1));
r->next->val=a[i];
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult:\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
}
==============================================================
> 12. Требования и свойства сортировок. Что когда лучше?
==============================================================
A: Kantor Ilia
Охарактеризуем сортировки по четырем параметрам:
1. Время сортировки.
2. Память - дополнительные затраты памяти, зависящие от размера
массива.
3. Устойчивость - устойчивая сортировка не меняет взаимного
расположения равных элементов.
Многие методы (например, HeapSort) по ходу работы так
перетряхивают массив, что равные элементы после сортировки
могут идти в совсем другой последовательности, нежели до этого.
4. Естественность поведения - эффективность метода при обработке уже
отсортированных, или частично отсортированных данных.
Естественный - значит учитывает этот факт и работает быстрее.
Hеестественный метод этот факт не учитывает, либо бывает, что
работает даже хуже(!).
Кроме того, есть два типа основных сортировок:
Распределяющая и ее вариации | Сортировка сравнениями
|
Основана на том, что число возможных | Пользуется лишь возможностью
значений ключа конечно. | прямого сравнения ключей и
(кроме, собственно, упорядоченности) | их упорядоченностью.
| Quicksort, Heapsort, Insertsort...
Сортировки сравнениями:
> SelectSort, BubbleSort, ShellSort - на практике не применяются.
> TreeSort - сортировка двоичным деревом
1. Общее быстродействие всегда O(nlogn).
2. Обычное дерево: n элементов (ключ + 2 указателя),
выбор с замещением: 2n-1 элементов
3. Устойчивости нет.
4. Поведение неестественно.
Примечание.
Поэтому TreeSort обычно применяют там, где
- построенное дерево можно с успехом применить для других задач.
- данные уже построены в 'дерево'. } не тратится
- данные можно считывать непосредственно в дерево. } лишняя
Hапример, при потоковом вводе с консоли или из файла. } память
Более подробно о выборе разновидности TreeSort смотри в соответствующем
вопросе.
> Insertsort - простые вставки.
1. Общее быстродействие - O( n^2 ), но ввиду простоты реализации
метода является наибыстрейшим для малых ( 12-20 элементов ) массивов и
списков.
2. Сортировка происходит 'на месте', т.е дополнительных затрат памяти нет.
3. Устойчивая.
4. Естественное поведение.
Примечание. Ввиду своих особенностей, метод хорош для частично
отсортированных данных.
> Quicksort - быстрая сортировка
1. Общее быстродействие Quicksort O( nlogn ) времени.
Случай n^2 возможен, но вероятность такого поведения
чрезвычайно мала. В общем и целом - наиболее быстрая сортировка
сравнениями для разупорядоченных массивов с 50 и более элементами.
2. Итерационный вариант требует logn памяти, рекурсивный - O(n).
3. Устойчивости нет.
4. Поведение неестественно. Уже практически отсортированный
массив будет сортироваться столько же, сколько и полностью
разупорядоченный.
> Heapsort - пирамидальная сортировка.
1. В 1.5 раза медленнее быстрой. Общее быстродействие всегда O(nlogn).
2. Сортировка 'на месте'
3. Устойчивости нет.
4. Поведение неестественно.
Примечание. Основное достоинство - сортировка не требует дополнительной
памяти, хороший средний случай. Ее элементы часто применяются в смежных
задачах.
> Mergesort - сортировка слиянием
1. Общее быстродействие - Theta(nlogn)
2. Theta(n)
3. Устойчивая.
4. Зависит от конкретной сортировки, основанной на принципе слияния.
Hа практике используются реализации с естественным поведением.
Примечание. Mergesort - общее название для обширного класса сортировок,
основанных на принципе слияния. Такие сортировки уступают QuickSort при
работе с массивами, но выигрывают на файлах и списках.
Распределяющая сортировка:
Для массивов:
Пусть всего n элементов, сортировка производится по k разрядам,
каждый может принимать до s различных значений. Числа k и s - константы,
известные до начала сортировки.
1. Общее быстродействие O(k(n+s)) [s иногда не учитывают вовсе]
2. Реализация со временным массивом O(n), [Radix Sort]
Реализация без временного массива O(logn) [Radix Exchange Sort]
3. Реализация со временным массивом устойчивая,
Реализация без временного массива неустойчивая.
4. Hеестественное поведение
Для списков:
1. Общее быстродействие O(k(n+s)) [s иногда не учитывают]
2. Дополнительной памяти не требуется, так как реорганизовывать
список можно просто через указатели
3. Устойчивая сортировка.
4. Hеестественное поведение.
> 12.1 Какая самая быстрая сортировка ?
===========================================================================
В общем случае:
Малые массивы/списки - менее 20 элементов => InsertSort
Большие массивы => QuickSort
Длинные списки/файлы => MergeSort
Для сортировок сравнениями давно доказана теорема о максимальном
быстродействии: Omega(nlogn) операций.
Если количество возможных различных ключей ненамного больше их общего
числа - то наибыстрейшей будет распределяющая сортировка и ее вариации:
Radix sort - 'радиксная', или 'распределяющая' сортировка.
Hапример, для больших массивов строк, целых чисел из небольшого промежутка.
Hа ее принципах основана Multiway Quicksort /MQS/ - быстрая с составными
ключами, на мой взгляд, неплохо удавшаяся попытка Jon Bentley и Robert
Sedgewick соединить преимущества Radix sort и QuickSort. Есть и другие шаги
в этом направлении..
Существует еще очень много различных сортировок, которые выходят за рамки
FAQ'а.
В конкретном случае надо смотреть по данным и имеющимся в наличии
ресурсам. В типичных случаях самыми простыми и довольно быстрыми
решениями будут стандартные методы.
> 12.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?
===========================================================================
Когда количество возможных различных ключей ненамного больше их общего
числа - распределяющая.
Различных ключей очень много, размер массива сравнительно небольшой
- сравнениями.
Время сортировки случайных целых чисел из промежутка [0..999]
Цифры могут меняться в зависимости от реализации, но соотношения
останутся приблизительно такими же.
n 10 20 30 40 50 100 200
Quick Sort 0.22 0.55 0.88 1.65 2.14 4.50 13.13
Merge Sort 0.33 0.88 1.37 1.97 2.74 6.37 14.78
Radix Sort 0.38 0.71 0.99 1.38 1.70 3.29 6.64
Иллюстрация замедления распределяющей сортировки при расширении
промежутка в два раза. Как следует из асимптотики, она работает в 2 раза
медленнее.
промежуток 0-999 промежуток 0-999999
n = 100 Сравнений Перемещений Время Сравнений Перемещений Время
Quick Sort 600 478 4.51 846 562 5.93
Merge Sort 543 672 6.43 538 672 6.38
Radix Sort 0 1000 3.29 0 2000 6.92
===========================================================================
> 13. Есть большой файл. Как его отсортировать ? Многофазная сортировка.
===========================================================================
В другом вопросе описывается простейшая сортировка слиянием. Ее вполне можно
применить к любому файлу и она будет работать.
иже мы разберем серьезно улучшенный алгоритм внешней сортировки слиянием,
работающий намного быстрее.
Многофазная сортировка слиянием.
Слиянием называется процесс объединения нескольких
упорядоченных серий(т.е упорядоченных списков) в одну.
Пример для 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 - общее число элементов серий.
В процессе сортировки мы будем оперировать лентами - структурами
данных, где в каждый момент нам доступен либо первый элемент, либо
следующий элемент после уже прочитанного.
В реальной ситуации в качестве лент выступают односвязные
списки или файлы.
Пусть у нас имеется 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
Стрелки показывают процесс слияния. Hапример, на втором шаге мы
слияем с f1, f2, f3, f4 и f6 на f5, пока одна из лент не опустеет.
В каждый момент времени слияние происходит на пустую ленту с остальных,
поэтому число требующихся проходов приблизительно равно log n.
N
Далее нам понадобятся числа Фибоначчи порядка p.
Они определяются следующим образом:
f_(i+1) = f_i + f_(i-1) + ... + f_(i-p) для i >=p,
f_p = 1,
f_i = 0 для 0 <= i < p.
Очевидно, обычные числа Фибоначчи имеют порядок 1.
В данном примере распределение начальных серий побрано искусственно.
Исходные числа серий для такой идеальной многофазной сортировки должны
быть суммами n-1 , n-2 , ... , 1 последовательных чисел Фибоначчи
порядка n-2.
Из этого следует, что наш алгоритм многофазного слияния применим только
к таким входным данным, в которых число серий есть сумма n-1 таких сумм
Фибоначчи.
Что делать, если число начальных серий не является такой идеальной суммой?
Ответ прост - предположим существование гипотетических пустых серий,
таких что сумма реальных и гипотетических серий дает идеальную сумму.
Пустые серии называются фиктивными или холостыми сериями.
Холостые серии по возможности равномерно распределяются по лентам, чтобы
реальное слияние (в котором холостые серии участвуют лишь 'в уме')
проходило с как можно большего количества лент.
Сначала все данные располагаются на одной ленте. Лента читается и
отрезки распределяются по другим лентам, имеющимся в системе. после того,
как созданы начальные отрезки, они сливаются, как описано выше. Один из
методов, который можно использовать для создания начальных отрезков, состоит
в чтении порции записей в память, их сортировке и записи результата на
ленту. Выбор с замещением(см. другой вопрос) позволяет нам получать более
длинные отрезки. Этот алгоритм работает с буфером, располагающимся в
оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие
шаги до тех пор, пока не будут исчерпаны входные данные:
=== Cut ===
<O> Bye, All <O>
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Sfaq 3/4 |
Ilia Kantor |
28 Mar 2002 22:13:30 |
|
|
