 |
|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Ilia Kantor 2:5020/1815.6 17 Jan 2002 02:39:26 To : All Subject : <без заголовка> -------------------------------------------------------------------------------- === Cut === i=2 06 |12 18 42 44 55 67 94 12 <-> 12 Вертикальной чертой отмечена граница уже отсортированной части массива. Очевидно, быстродействие алгоритма можно оценить как Omega(N^2), так как выбор наибольшего элемента на каждом шаге требует Omega(N) операций. Построим структуру данных, позволяющую выбирать максимальный элемент за O(logn) времени. Тогда общее быстродействие сортировки будет O(nlogn). Эта структура также должна позволять быстро вставлять новые элементы (чтобы быстро ее построить из исходного массива) и удалять максимальный элемент (он будет помещаться в уже отсортированный конец массива). Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором - все узлы имеют глубину k или k-1 - дерево сбалансированное. - при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо. - выполняется 'свойство пирамиды': каждый элемент <= родителя. Пример 1: h1 Общий вид пирамиды высоты k=4 / \ / \ 'Свойство пирамиды' при такой картинке / \ можно записать в виде / \ h_i >= h_2i / \ h_i >= h_2i+1 / \ h2 h3 / \ / \ / \ / \ / \ / \ h4 h5 h6 h7 } 3 уровень / \ / \ / h8 h9 h10 h11 h12 } 4 уровень, заполнен слева направо. Пример 2: 94 / \ / \ / \ / \ / \ 55 44 / \ / \ / \ / \ 06 42 18 12 Как хранить пирамиду? Проще всего поместить ее в массив. Схема соответствия: В массиве именно пирамида: A[1] - корень дерева | Для массива, представляющего A[2i] - левый сын A[i] | пирамиду, A[i] >= A[2i] A[2i+1] - правый сын A[i] | A[i] >= A[2i+1] Для примера 2 массив будет 94 55 44 6 42 18 12. Плюсы такого подхода очевидны: - для хранения пирамиды не нужно никакой специальной структуры, никаких дополнительных переменных, нужно лишь понимать схему. - узлы хранятся от вершины и вниз, уровень за уровнем. - узлы одного уровня хранятся в массиве слева направо. Далее я часто буду говорить, что задана пирамида, давая ее в виде массива. Восстановить ее как геометрический объект легко - достаточно вспомнить схему хранения. а примере 1 (см. выше) показана пирамида, восстановленная из массива h[1..12]. Фаза 1 сортировки: построение пирамиды Если у нас уже готова пирамида a[k+1..N] - можно расширить ее до пирамиды a[k..N], проведя для a[k] процедуру добавления элемента. Процедура добавления элемента в готовую пирамиду 1. Hовый элемент Х помещаем в вершину дерева. 2. Смотрим на сыновей слева и справа - выбираем наибольший. 3. Если этот элемент больше Х - меняем их местами и идем у шагу 2 уже относительно сына. Иначе конец процедуры. Реализация процедуры на Си: downHeap(int a[], int k, int N) /* До процедуры: a[k+1..N] - пирамида */ /* После: a[k..N] - пирамида */ { int newElt, child; newElt=a[k]; while(k <= N/2) /* k has child(s) */ { child = 2*k; /* pick larger child */ if(child < N && a[child] < a[child+1]) child++; if(newElt >= a[child]) break; /* else */ a[k] = a[child]; /* move child up */ k = child; } a[k] = newElt; }/*downHeap*/ Учитывая, что высота пирамиды h <= log N, downheap требует O(logN) времени. 2 Пусть дан произвольный массив a[1..N], который надо отсортировать. ачать построение пирамиды можно с a[k..N], k = [N/2] Этот массив обладает свойством пирамиды, так как для него не существует индексов i,j: j = 2*i ( или j = 2*i+1 ). Далее расширяем ее, по очереди вызывая downheap для остальных элементов справа налево: for(i=N/2; i >= 1; i--) downHeap(a, i, N); Вот иллюстрация процесса для пирамиды из 8-и элементов: 44 55 12 42 // 94 18 06 67 справа - часть массива, 44 55 12 // 67 94 18 06 42 начинающаяся с k=8/2=4 44 55 // 18 67 94 12 06 42 44 // 94 18 67 55 12 06 42 остальные элементы добавляются // 94 67 18 44 55 12 06 42 один за другим, справа налево. Фаза 2: собственно сортировка Берем верхний элемент пирамиды (первый в массиве) - меняем с последним местами, затем вызываем downheap для построения пирамиды из оставшегося массива a[1..N-1]. downheap(a, 1, N-1) То есть кладем бывший последний элемент массива на вершину вместо снятого и передвигаем его на нужное место, восстанавливая пирамидальность. При этом, как мы и хотели (!), максимальный элемент придет на вершину(первое место в массиве) всего за log_2(N) операций. Меняем местами верхний элемент пирамиды (первый в массиве) и последний в текущем массиве (т.е уже (N-1)-ый). И так далее, всего N шагов. for(i=N; i > 1; i--) { temp = a[i]; a[i]=a[1]; /* largest of a[1..i] */ a[1]=temp; downHeap(a,1,i-1); /* restore a[1..i-1] heap */ } Иллюстрация на нашем массиве, уже построенном в пирамиду. 94 67 18 44 55 12 06 42 // 67 55 44 06 42 18 12 // 94 55 42 44 06 12 18 // 67 94 44 42 18 06 12 // 55 67 94 42 12 18 06 // 44 55 67 94 18 12 06 // 42 44 55 67 94 12 06 // 18 42 44 55 67 94 06 // 12 18 42 44 55 67 94 Исходник сортировки целиком: heapSort(int a[], int N) /* sort a[1..N], N.B. 1 to N */ { int i, temp; for(i=N/2; i >= 1; i--) downHeap(a, i, N); /* a[1..N] is now a heap */ for(i=N; i > 1; i--) { temp = a[i]; a[i]=a[1]; /* largest of a[1..i] */ a[1]=temp; downHeap(a,1,i-1); /* restore a[1..i-1] heap */ } }/*heapSort*/ Для построения пирамиды нашим способом требуется NlogN операций, затем мы N-1 раз вызываем downheap, таким образом общее быстродействие - P(NlogN). Прекрасной характеристикой этого метода является то, что среднее число пересылок - (N*log N)/2, и отклонения от этого значения сравнительно малы. P.S Существует два метода Heapsort, одинаковых по общему быстродействию. Выше я изложил только один из них, более короткий в описании. В частности, фазу построения начальной пирамиды можно завершить и за O(N) операций. ============================================================== > 8. Описание и исходник MergeSort (сортировка слиянием). ============================================================== Under construction yet. =========================================================================== > 9. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка > ? =========================================================================== A: Kantor Ilia Пусть имеем максимум по 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(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'; } Примечания. К сожалению, или к счастью, единица информации в современной технике способна принимать лишь 2 значения: 1 и 0. А значит, любые компьютерные данные тоже могут принимать ограниченное количество значений, так как состоят из некоторого числа битов ;-)). Таким образом, распределяющая сортировка потенциально применима где угодно. Другое дело, что если разрядность данных большая по сравнению с общим количеством элементов, то скорость работы оставит желать много лучшего. Алгоритм, описанный выше, очевидно, требует O(n) памяти. Существует похожий алгоритм, использующий лишь O(logn). Модифицированная Radix Sort: Будем сортировать по каждой позиции символа 'на месте', начиная справа: сначала сортируем по первой позиции, затем к каждой части массива, относящейся к одному и тому же значению, рекурсивно применяем ту же процедуру и т.д. Этот вариант называется 'Radix exchange sort' и представляет собой скорее разновидность QuickSort. а мой взгляд, она объединяет больше плохих черт обоих методов, нежели хороших, но вполне может пригодиться в какой-то ситуации. ============================================================== > 10. Требования и свойства сортировок. Что когда лучше? ============================================================== A: Kantor Ilia Охарактеризуем сортировки по четырем параметрам: 1. Время сортировки 2. Память - дополнительные затраты памяти, зависящие, от размера массива. 3. Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. Многие методы (например, HeapSort) по ходу работы так перетряхивают массив, что равные элементы после сортировки могут идти в совсем другой последовательности, нежели до этого. 4. Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Естественный - значит учитывает этот факт и работает быстрее. Кроме того, есть два типа основных сортировок: Распределяющая и ее вариации | Сортировка сравнениями | Основана на том, что число возможных | Пользуется лишь возможностью значений ключа конечно. | прямого сравнения ключей и | их упорядоченностью. | Quicksort, Heapsort, Insertsort... Сортировки сравнениями: > SelectSort, ShellSort - на практике не применяются. > 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. Работа ненамного ускоряется при сортировке уже отсортированных данных. В общем поведение неестественно. Примечание. Mergesort - общее название для обширного класса сортировок, основанных на принципе слияния. Такие сортировки уступают QuickSort и HeapSort при работе с массивами, но сильно выигрывают на файлах и списках. Распределяющая сортировка: Пусть всего n элементов, сортировка производится по k разрядам, каждый может принимать до s различных значений. Числа k и s - константы, известные до начала сортировки. 1. Общее быстродействие O(k(n+s)) 2. Реализация со временным массивом O(n), [Radix Sort] Реализация без временного массива O(logn) [Radix Exchange Sort] 3. Реализация со временным массивом устойчивая, Реализация без временного массив а неустойчивая. 4. еестественное поведение > 10.1 Какая самая быстрая сортировка ? =========================================================================== В общем случае: Малые массивы/списки - менее 20 элементов => InsertSort Большие массивы => QuickSort Длинные списки/файлы => MergeSort Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: Omega(nlogn). Если количество возможных различных ключей ненамного больше их общего числа - то наибыстрейшей будет распределяющая сортировка и ее вариации: Radix sort - 'радиксная', или 'распределяющая' сортировка. апример, для больших массивов строк, целых чисел из небольшого промежутка. а ее принципах основана Multiway Quicksort /MQS/ - быстрая с составными ключами, на мой взгляд, неплохо удавшаяся попытка Jon Bentley и Robert Sedgewick соединить преимущества Radix sort и QuickSort. Есть и другие шаги в этом направлении.. Существует еще очень много различных сортировок, которые выходят за рамки FAQ'а. В конкретном случае надо смотреть по данным и имеющимся в наличии ресурсам, однако в типичных случаях самыми простыми и довольно быстрыми решениями станут методы из S0rting FAQ. > 10.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 =========================================================================== > 11. Есть большой файл. Как его отсортировать ? =========================================================================== Многофазная сортировка Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну. Пример для 3-х серий, слияемых на 4-ю: 3 7 9 3 7 9 3 7 9 7 9 7 9 { 2 4 6 1 { 2 === Cut === ъщю До следующих встреч, All ющъ --- GoldEd 3.00.Alpha4+ * Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39463c462b5f.html, оценка из 5, голосов 10
|
|
|