Базы данныхИнтернетКомпьютерыОперационные системыПрограммированиеСетиСвязьРазное
Поиск по сайту:
Подпишись на рассылку:

Назад в раздел

FAQ по СОРТИРОВКАМ.

eManual.ru - электронная документация

Секция 1 из 2 - Предыдущая - Следующая

From: Ilia Kantor <Ilia.Kantor@p6.f1815.n5020.z2.fidonet.org> Date: Fri, 26 Jan 2001 16:55:14 +0300 Sorting FAQ V1.1 FAQ по СОРТИРОВКАМ версия 1.1 > Вопросы 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 ) ? ==================================================================== A: Kantor Ilia - Tomas Niemann. Оценки времени исполнения. Cимвол O(). Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(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 раз эффективнее. Это значит лишь то, что их время возрастает приблизительно как функция n*log n. > За функцию берется количество операций, возрастающее быстрее всего. То есть если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n^2) раз, то общая сложность - O(n^2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут тормозить куда больше, нежели медленные, но редкие умножения. > Основание логарифма не пишется. Причина этого весьма проста. Пусть у нас есть O(log2_n). Но log2_n = log3_n / log3_2, а log3_2, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O(log2_n) = O( log3_n). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла. ==================================================================== > 2. Какие на сегодняшний день самые эффективные методы сортировки ? ==================================================================== A: Kantor Ilia быстрая сортировка, распределяющая сортировка и быстрая сортировка с составными ключами, которая слишком сложна для ФАКа. Для прикладных задач, использующих элементы сортировки также очень полезна пирамидальная сортировка. ==================================================================== > 3. Сортировка простыми вставками. ==================================================================== A: Kantor Ilia - Nicolas Virt - Tomas Niemann ;-)) Алгоритм Все элементы условно разделяются на готовую последовательность 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 Пример на Си - 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; } } } Улучшения На практике для увеличения быстроты, но не асимптотики, можно произвести несколько улучшений: 1. В качестве центрального для функции partition выбирается элемент, расположенный в середине. Такой выбор улучшает оценку среднего времени работы, если массив упорядочен лишь частично. Наихудшая для этой реализации ситуация возникает в случае, когда каждый раз при работе partition в качестве центрального выбирается максимальный или минимальный элемент. 1' Можно выбрать средний из первого, последнего и среднего элементов. Maxim Razin: Тогда количество проходов уменьшится в 7/6 раз. 2. Для коротких массивов вызывается сортировка вставками. Из-за рекурсии и других "накладных расходов" быстрый поиск оказывается не столь уж быстрым для коротких массивов. Поэтому, если в массиве меньше 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: Kantor Ilia - Nicolas Virt Назовем пирамидой последовательность элементов hl , hl+1 , ... , hr такую, что hi <= h2i hi <= h2i+1 для всякого i = l , ... , r/2 Геометрическая интерпретация пиромиды: h1 / / / / / h2 h3 / / / / h4 h5 h6 h7 / / / / h8 h9 h10 h11 h12 h13 h14 h15 Для последовательности 06 42 12 55 94 18 44 06 / / / / / 42 12 / / / / 55 94 18 44 Добавление элемента в готовую пирамиду 1. Новый элемент Х помещаем в вершину дерева. 2. Смотрим на элемент слева и элемент справа - выбираем наименьший. 3. Если этот элемент меньше Х - меняем их местами и идем у шагу 2. Иначе конец процедуры. Фаза 1: построение пирамиды Пусть дан массив h1 ... hn . Ясно, что элементы hn/2 + 1 ... hn уже образуют 'нижний ряд' пирамиды, так как не существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То есть тут упорядочивания не требуется. На каждом шаге добавляется новый элемент слева и 'просеивается' на место. Вот иллюстрация процесса для пирамиды из 8-и элементов: 44 55 12 42 // 94 18 06 67 44 55 12 // 42 94 18 06 67 44 55 // 06 42 94 18 12 67 44 // 42 06 55 94 18 12 67 // 06 42 12 55 94 18 44 67 Фаза 2: сортировка Для того, чтобы рассортировать элементы, необходимо выполнить n шагов просеивания: после каждого шага очередной элемент берется с вершины пирамиды. На каждом шаге берем последний элемент Х, верхний элемент пирамиды помещается на его место, а Х просеивается на свое 'законное'. В этом случае необходимо совершить n - 1 шагов. Пример: 06 42 12 55 94 18 44 67 // 12 42 18 55 94 67 44 // 06 18 42 44 55 94 67 // 12 06 42 55 44 67 94 // 18 12 06 44 55 94 67 // 42 18 12 06 55 67 94 // 44 42 18 12 06 67 94 // 55 44 42 18 12 06 94 // 67 55 44 42 18 12 06 Ну вот мы м получили отсортированную последовательность, только в обратном порядке. Изменяя сравнения на противоположные, получаем функцию Heapsort на Паскале Прекрасной характеристикой этого метода является то, что среднее число пересылок - (n*log n)/2 и отклонения от этого значения сравнительно малы. { сортируем массив типа 'item' по ключу 'a.key' } procedure Heapsort; var i,l: index; x: item; procedure sift; label 13; var i, j: index; begin i := l; j := 2*i; x := a[i]; while j <= r do begin if j < r then if a[j].key < a[j+1].key then j := j+1; if x.key >= a[j].key then goto 13; a[i] := a[j]; i := j; j := 2*i end; 13: a[i] := x end; begin l := (n div 2) + 1; r := n; while l > 1 do begin l := l - 1; sift end; while r > 1 do begin x := a[l]; a[l] := a[r]; a[r] := x; r := r - 1; sift end end { heapsort } ============================================================== > 6. Требования QuickSort и HeapSort. InsertSort... Что лучше ? ============================================================== A: Kantor Ilia > Простые вставки. Общее быстродействие - O( n^2 ), но ввиду простоты метода, является наибыстрейшим для малых ( 12-20 элементов ) массивов. Естественное поведение. Легко прибавлять новые элементы. Ввиду своих особенностей, чрезвычайно хорош для списков. Сортировка не требует дополнительной памяти. > Быстрая сортировка Общее быстродействие - O( nlogn ). Случай n^2 теоретически возможен, но крайне [ 1 / (n^logn) ] маловероятен. В общем и целом - наиболее быстрая сортировка сравнениями для разупорядоченных массивов с >50 элементами. Поведение неестественно. Уже практически отсортированный массив будет сортироваться столько же, сколько и полностью разупорядоченный. Итерационный вариант требует logn памяти, рекурсивный - O(n). > Пирамидальная сортировка. В 1.5 раза медленнее быстрой. Наихудшего случая нет - всегда O(nlogn). Практически, ее элементы часто применяются в смежных задачах. Поведение неестественно. Основное достоинство - сортировка не требует дополнительной памяти. ==================================================================== > 7. Какая самая быстрая сортировка ? ==================================================================== A: Kantor Ilia Давайте разберемся раз и навсегда. Есть два типа сортировок: Распределяющая и ее вариации | Сортировка сравнениями | Основана на том, что число возможных | Пользуется лишь возможностью значений ключа конечно. | прямого сравнения ключей и | их упорядоченностью. | Quicksort, Heapsort... Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: O( nlogn ). Для сортировок распределением это - O(n). Быстрее сортировать нельзя. Итак, наибыстрейшие сортировки - Quicksort - быстрая, Radix sort - распределяющая и их молодой гибрид: Multiway Quicksort /MQS / - быстрая с составными ключами. апример, для строк. Вообще, нужно смотреть по данным и имеющимся в наличии ресурсам, но в типичных случаях наибыстрейшими решениями станут <см выше>. =========================================================================== > 8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка > ? =========================================================================== A: Kantor Ilia К сожалению, или к счастью, единица информации в современной технике способна применять лишь 2 значения: 1 и 0. А значит, любые компьютерные данные тоже могут принимать ограниченное количество значений, так как состоят из некоторого числа битов ;-)). Пусть имеем максимум по k байт в каждом ключе ( хотя, за элемент сортировки вполне можно принять и что-либо другое. k должно быть известно заранее, до сортировки. Разрядность данных ( количество возможных значений элементов k) - m. Если мы сортируем слова, то элемент сортировки - буква. m = 33. Если в самом длинном слове 10 букв, k = 10. Обычно мы будем сортировать данные по ключам из k байт, m=255. ---------------------------------------------------------------------- Пусть у нас есть массив 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. Например, 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 ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой сортировки' ! Реализация на C++ для long int'ов. Сам не делал - валялась в и-нете. #include <iostream.h> #include < stdlib.h> #include < string.h> void radix (int byte, long N, long *source, long *dest) { long count[256]; long index[256]; 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) { 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'; } =========================================================================== > 9. Что быстрее: распределяющая сортировка или QuickSort ? =========================================================================== A: Kantor Ilia Когда количество возможных различных ключей ненамного больше их общего числа - распределяющая. Различных ключей очень много, размер массива сравнительно небольшой - быстрая. =========================================================================== > 10. Есть большой файл. Как его отсортировать ? =========================================================================== A: Kantor Ilia - Tomas Niemann Многофазная сортировка Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну. Пример для 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 Каждый pаз мы беpем све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 В каждый момент времени слияние происходит на пустую ленту с остальных, поэтому число требующихся проходов приблизительно равно log N n. В данном примере распределение начальных серий побрано искусственно. Для идеальной сортировки исходные числа серий должны быть суммами n - 1 , n - 2 , ... , 1 последовательных чисел Фибоначчи порядка n - 2. Число Фибоначчи порядка p определяются следующим образом: fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p, fp(p) = 1, fi(p) = 0 для 0 <= i < p. Очевидно, обычные числа Фибоначчи имеют порядок 1. Поэтому предположим существование фиктивных серий, таких что сумма фиктивных с реальными дает идеальное число. Сначала все данные располагаются на одной ленте. Лента читается и отрезки распределяются по другим лентам, имеющимся в системе. после того, как созданы начальные отрезки, они сливаются, как описано выше. Один из методов, который можно использовать для создания начальных отрезков, состоит в чтении порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут исчерпаны входные данные: * Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >= значения ключа последней прочитанной записи. * Если все "старые" ключи меньше последнего ключа, то мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве первого элемента следующего отрезка. * Записываем выбранную запись. * Заменяем выбранную и записанную запись на новую из входного файла. На следующей таблице выбор с замещением иллюстрируются для совсем маленького файла. Начало файла - справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего. Шаг Вход Буфер Выход A 5-3-4-8-6-7 B 5-3-4-8 6-7 C 5-3-4 8-7 6 D 5-3 8-4 7-6 E 5 3-4 8-7-6 F 5-4 3 | 8-7-6 G 5 4-3 | 8-7-6 H 5-4-3 | 8-7-6 Обратите внимание мы храним записи в буфере до тех пор, пока не наступит время записать их в выходной файл. Если вход случаен, средняя длина отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот метод, вообще говоря, более эффективен промежуточных, частичных сортировок. Прочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь log n сравнений. Реализация В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков. ----------------------------------------------------------- /* внешняя сортировка */ #include <stdio.h> #include <stdlib.h> #include <string.h> /* темплейт для временных файлов (формат 8.3) */ #define FNAME "_sort%03d.dat" #define LNAME 13 /* операторы сравнения */ #define compLT(x,y) (x < y) #define compGT(x,y) (x > y) /* определяем сортируемые записи */ #define LRECL 100 typedef int keyType; typedef struct recTypeTag { keyType key; /* ключ, по которому сортируем */ #if LRECL char data[LRECL-sizeof(keyType)]; /* остальные поля */ #endif } recType; typedef enum {false, true} bool; typedef struct tmpFileTag { FILE *fp; /* указатель на файл */ char name[LNAME]; /* имя файла */ recType rec; /* последняя прочитанная запись */ int dummy; /* номер холостых проходов */ bool eof; /* флаг конца пробега end-of-file */ bool eor; /* флаг конца прохода end-of-run */ bool valid; /* верно, если запись - годная */ int fib; /* идеальное число Фибоначчи */

Секция 1 из 2 - Предыдущая - Следующая



  • Главная
  • Новости
  • Новинки
  • Скрипты
  • Форум
  • Ссылки
  • О сайте




  • Emanual.ru – это сайт, посвящённый всем значимым событиям в IT-индустрии: новейшие разработки, уникальные методы и горячие новости! Тонны информации, полезной как для обычных пользователей, так и для самых продвинутых программистов! Интересные обсуждения на актуальные темы и огромная аудитория, которая может быть интересна широкому кругу рекламодателей. У нас вы узнаете всё о компьютерах, базах данных, операционных системах, сетях, инфраструктурах, связях и программированию на популярных языках!
     Copyright © 2001-2024
    Реклама на сайте