|
25.05.2003, 14:28
| #1 |
| »  Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 |  Faq по СОРТИРОВКАМ
Ликбез для понимания важной информации: Что означает символ O(n)? Почему не пишется основание логарифма: O (log n)? Оценки времени исполнения. Cимвол O(). Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Hапример, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n). Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n^2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. Code: 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 Если оба алгоритма, например, O ( n*log n ), то это отнюдь не значит, что они одинакого эффективны. Символ О не учитывает константу, то есть первый может быть, скажем в 1000 раз эффективнее. Это значит лишь то, что их время возрастает приблизительно как функция n*log n. За функцию берется количество операций, возрастающее быстрее всего. То есть если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n^2) раз, то общая сложность - O(n^2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут тормозить куда больше, нежели медленные, но редкие умножения. Основание логарифма не пишется. Причина этого весьма проста. Пусть у нас есть O(log2_n). Hо log2_n = log3_n / log3_2, а log3_2, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O(log2_n) = O( log3_n). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла.
__________________ •·•· ·•·· ·· •·•· •·• |
 |
|
25.05.2003, 14:29
| #2 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 |  Сортировка простыми вставками.
Сортировка простыми вставками. Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-И элемент входной последовательности и вставляем его на нужное место в готовую. Пример: Code: 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 \\ Просеивание может кончиться при двух условиях: 1. Hайден ai с ключом, меньшим x. 2. Достигнут конец готовой последовательности. Метод хорош устойчивостью сортировки, удобством для реализации в списках и, самое главное, естественностью поведения. То есть уже частично отсортированный массив будут досортирован им гораздо быстрее чем многими 'продвинутыми' методами. Анализ Code: Число сравнений
минимальное: 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 Code:
--------------------------------------------------------------------
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;
}
} |
| |
|
25.05.2003, 14:34
| #3 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 | QuickSort (быстрая сортировка)
Описание QuickSort (быстрая сортировка). Основной алгоритм Выберем случайным образом какой-то элемент с у просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший У. Поменяем их местами и продолжим процесс просмотра с обменом, пока просмотры не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами, меньшими с у ночаяв - с ключами, большими У. Этот шаг называется разделением. у - центром. К получившимся частям рекурсивно применяем ту же процедуру. В результате получается очень эффективная сортировка Улучшения Hа практике для увеличения быстроты, но не асимптотики, можно произвести несколько улучшений: 1. В качестве центрального для функции partition выбирается элемент, расположенный в середине. Такой выбор улучшает оценку среднего времени работы, если массив упорядочен лишь частично. Hаихудшая для этой реализации ситуация возникает в случае, когда каждый раз при работе partition в качестве центрального выбирается максимальный или минимальный элемент. 1' Можно выбрать средний из первого, последнего и среднего элементов. Maxim Razin: Тогда количество проходов уменьшится в 7/6 раз. 2. Для коротких массивов вызывается сортировка вставками. Из-за рекурсии и других "накладных расходов" быстрый поиск оказывается не столь уж быстрым для коротких массивов. Поэтому, если в массиве меньше 12 элементов, вызывается сортировка вставками. Пороговое значение не критично - оно сильно зависит от качества генерируемого кода. 3. Если последний оператор функции является вызовом этой функции, говорят о хвостовой рекурсии. Ее имеет смысл заменять на итерации - в этом случае лучше используется стек. 4. После разбиения сначала сортируется меньший раздел. Это также приводит к лучшему использованию стека, поскольку короткие разделы сортируются быстрее и им нужен более короткий стек. Требования к памяти уменьшаются с n до log n. Пример, входящий в стандартную реализацию Си использует многие из этих улучшений. Стандартная реализация итерационной QuickSort Code: ------------------------------------------------
#include
#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;
}
}
}
} |
| |
|
25.05.2003, 14:37
| #4 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 | HeapSort (пирамидальная сортировка)
Описание и исходник HeapSort (пирамидальная сортировка). Hазовем пирамидой последовательность элементов hl , hl+1 , ... , hr такую, что hi <= h2i hi <= h2i+1 для всякого i = l , ... , r/2 Геометрическая интерпретация пирамиды: Code: 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. Hовый элемент у помещаем в вершину дерева. 2. Смотрим на элемент слева и элемент справа - выбираем наименьший. 3. Если этот элемент меньше у - меняем их местами и идем у шагу 2. Иначе конец процедуры. Фаза 1: построение пирамиды Пусть дан массив h1 ... hn . Ясно, что элементы hn/2 + 1 ... hn уже образуют 'нижний ряд' пирамиды, так как не существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То есть тут упорядочивания не требуется. Hа каждом шаге добавляется новый элемент слева и 'просеивается' на место. Вот иллюстрация процесса для пирамиды из 8-и элементов: Code: 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 Для того, чтобы рассортировать элементы, необходимо выполнить n шагов просеивания: после каждого шага очередной элемент берется с вершины пирамиды. Hа каждом шаге берем последний элемент у, верхний элемент пирамиды помещается на его место, а у просеивается на свое 'законное'. В этом случае необходимо совершить n - 1 шагов. Пример: Code: 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 и отклонения от этого значения сравнительно малы. Code: { сортируем массив типа '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 } |
| |
|
25.05.2003, 14:38
| #5 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 |
Требования QuickSort и HeapSort. InsertSort... Что лучше? Простые вставки. Общее быстродействие - O( n^2 ), но ввиду простоты метода, является наибыстрейшим для малых ( 12-20 элементов ) массивов. Естественное поведение. Легко прибавлять новые элементы. Ввиду своих особенностей, чрезвычайно хорош для списков. Сортировка не требует дополнительной памяти. Быстрая сортировка Общее быстродействие - O( nlogn ). Случай n^2 теоретически возможен, но крайне [ 1 / (n^logn) ] маловероятен. В общем и целом - наиболее быстрая сортировка сравнениями для разупорядоченных массивов с >50 элементами. Поведение неестественно. Уже практически отсортированный массив будет сортироваться столько же, сколько и полностью разупорядоченный. Итерационный вариант требует logn памяти, рекурсивный - O(n). Пирамидальная сортировка. В 1.5 раза медленнее быстрой. Hаихудшего случая нет - всегда O(nlogn). Практически, ее элементы часто применяются в смежных задачах. Поведение неестественно. Основное достоинство - сортировка не требует дополнительной памяти. |
| |
|
25.05.2003, 14:40
| #6 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 |
Какая самая быстрая сортировка? Давайте разберемся раз и навсегда. Есть два типа сортировок: Code: Распределяющая и ее вариации | Сортировка сравнениями
|
Основана на том, что число возможных | Пользуется лишь возможностью
значений ключа конечно. | прямого сравнения ключей и
| их упорядоченностью.
| Quicksort, Heapsort... о максимальном быстродействии: O(nlog n). Для сортировок распределением это - O(n). Быстрее сортировать нельзя. Итак, наибыстрейшие сортировки - Quicksort - быстрая, Radix sort - распределяющая и их молодой гибрид: Multiway Quicksort /MQS / - быстрая с составными ключами. например, для строк. |
| |
|
25.05.2003, 14:44
| #7 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 | Многофазная сортировка
Многофазная сортировка Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну. Пример для 3-У серий, слияемых на 4-А: [CODE] 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 [CODE] Каждый pаз мы беpем свеpху наименьший элемент. Таким образом, каждая операция слияния серий требует n пересылок элементов, где n - общее число элементов серий. Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем слиять элементы со входных лент на выходную, пока какая-либо из них не опустеет. Затем она станет входной. Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии обозначены буквами fi, в таблице - количество элементов. Code: Тип 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. Поэтому предположим существование фиктивных серий, таких что сумма фиктивных с реальными дает идеальное число. Сначала все данные располагаются на одной ленте. Лента читается и отрезки распределяются по другим лентам, имеющимся в системе. после того, как созданы начальные отрезки, они сливаются, как описано выше. Один из методов, который можно использовать для создания начальных отрезков, состоит в чтении порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут исчерпаны входные данные: Выбрать запись с наименьшим ключом, в.И. с ключом, значение которого >= значения ключа последней прочитанной записи. Если все "старые" ключи меньше последнего ключа, то мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве первого элемента следующего отрезка. Записываем выбранную запись. Заменяем выбранную и записанную запись на новую из входного файла. Hа следующей таблице выбор с замещением иллюстрируются для совсем маленького файла. Hазало дайла - справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего. Code: Шаг Вход Буфер Выход
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, которая производит многофазное слияние отрезков. Code: /* внешняя сортировка */
#include
#include
#include
/* темплейт для временных файлов (формат 8.3) */
#define FNAME "_sortd.dat"
#define LNAME 13
/* операторы сравнения */
#define compLT(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; /* идеальное число Фибоначчи */
} tmpFileType;
static tmpFileType **file; /* массив информации о временных файлах */
static int nTmpFiles; /* количество временных файлов */
static char *ifName; /* имя входного файла */
static char *ofName; /* имя выходного файла */
static int level; /* уровень проходов */
static int nNodes; /* количество узлов для дерева выбора */
void deleteTmpFiles(void) {
int i;
/* удалить сливаемые файлы и освободить ресурсы */
if (file) {
for (i = 0; i fp) fclose(file[i]->fp);
if (*file[i]->name) remove(file[i]->name);
free (file[i]);
}
}
free (file);
}
}
void termTmpFiles(int rc) {
/* очистить файлы */
remove(ofName);
if (rc == 0) {
int fileT;
/* file[T] содержит результаты */
fileT = nTmpFiles - 1;
fclose(file[fileT]->fp); file[fileT]->fp = NULL;
if (rename(file[fileT]->name, ofName)) {
perror("io1");
deleteTmpFiles();
exit(1);
}
*file[fileT]->name = 0;
}
deleteTmpFiles();
}
void cleanExit(int rc) {
/* очистить временные файлы и выйти */
termTmpFiles(rc);
exit(rc);
}
void *safeMalloc(size_t size) {
void *p;
/* Безопасно выделить память и инициализоваться */
if ((p = calloc(1, size)) == NULL) {
printf("error: malloc failed, size = %d\n", size);
cleanExit(1);
}
return p;
}
void initTmpFiles(void) {
int i;
tmpFileType *fileInfo;
/* инициализовать файлы для слияния */
if (nTmpFiles < 3) nTmpFiles = 3;
file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
for (i = 0; i < nTmpFiles; i++) {
file[i] = fileInfo + i;
sprintf(file[i]->name, FNAME, i);
if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
perror("io2");
cleanExit(1);
}
}
}
recType *readRec(void) {
typedef struct iNodeTag { /* внутренний узел */
struct iNodeTag *parent;/* предок внутреннего узла */
struct eNodeTag *loser; /* внешний проигравший */
} iNodeType;
typedef struct eNodeTag { /* внешний узел */
struct iNodeTag *parent;/* предок внешнего узла */
recType rec; /* вводимая запись */
int run; /* номер прохода */
bool valid; /* вводимая запись годна */
} eNodeType;
typedef struct nodeTag {
iNodeType i; /* внутренний узел */
eNodeType e; /* внешний узел */
} nodeType;
static nodeType *node; /* массив узлов дерева выбора */
static eNodeType *win; /* новый победитель */
static FILE *ifp; /* входной файл */
static bool eof; /* верно, если конец входного файла */
static int maxRun; /* максимальное число проходов */
static int curRun; /* номер текущего прохода */
iNodeType *p; /* указатель на внутренние узлы */
static bool lastKeyValid; /* верно, если lastKey годен */
static keyType lastKey; /* последний ключ lastKey записан */
/* Прочитать следующую запись путем выбора с замещением */
/* Проверка на первый выхов */
if (node == NULL) {
int i;
if (nNodes < 2) nNodes = 2;
node = safeMalloc(nNodes * sizeof(nodeType));
for (i = 0; i < nNodes; i++) {
node[i].i.loser = &node[i].e;
node[i].i.parent = &node[i/2].i;
node[i].e.parent = &node[(nNodes + i)/2].i;
node[i].e.run = 0;
node[i].e.valid = false;
}
win = &node[0].e;
lastKeyValid = false;
if ((ifp = fopen(ifName, "rb")) == NULL) {
printf("error: file %s, unable to open\n", ifName);
cleanExit(1);
}
}
while (1) {
/* заместить предыдущего победителя новой записью */
if (!eof) {
if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
if ((!lastKeyValid || compLT(win->rec.key, lastKey))
&& (++win->run > maxRun))
maxRun = win->run;
win->valid = true;
} else if (feof(ifp)) {
fclose(ifp);
eof = true;
win->valid = false;
win->run = maxRun + 1;
} else {
perror("io4");
cleanExit(1);
}
} else {
win->valid = false;
win->run = maxRun + 1;
}
/* привести в порядок предков победителя и проигравшего */
p = win->parent;
do {
bool swap;
swap = false;
if (p->loser->run < win->run) {
swap = true;
} else if (p->loser->run == win->run) {
if (p->loser->valid && win->valid) {
if (compLT(p->loser->rec.key, win->rec.key))
swap = true;
} else {
swap = true;
}
}
if (swap) {
/* p должно быть победителем */
eNodeType *t;
t = p->loser;
p->loser = win;
win = t;
}
p = p->parent;
} while (p != &node[0].i);
/* конец прохода ? */
if (win->run != curRun) {
/* win->run = curRun + 1 */
if (win->run > maxRun) {
/* конец вывода */
free(node);
return NULL;
}
curRun = win->run;
}
/* вывести верх дерева */
if (win->run) {
lastKey = win->rec.key;
lastKeyValid = true;
return &win->rec;
}
}
}
void makeRuns(void) {
recType *win; /* победитель */
int fileT; /* прошлый файл */
int fileP; /* следующий за прошлым файлом */
int j; /* выбираем file[j] */
/* Сделать инициализационные проходы через выбор с замещением.
* Проходы напианы с использованием распределения Фибоначчи.
*/
/* инициализовать файловые структуры */
fileT = nTmpFiles - 1;
fileP = fileT - 1;
for (j = 0; j fib = 1;
file[j]->dummy = 1;
}
file[fileT]->fib = 0;
file[fileT]->dummy = 0;
level = 1;
j = 0;
win = readRec();
while (win) {
bool anyrun;
anyrun = false;
for (j = 0; win && j <= fileP; j++) {
bool run;
run = false;
if (file[j]->valid) {
if (!compLT(win->key, file[j]->rec.key)) {
/* добавить к существующему проходу */
run = true;
} else if (file[j]->dummy) {
/* начать новый проход */
file[j]->dummy--;
run = true;
}
} else {
/* первый проход в файле */
file[j]->dummy--;
run = true;
}
if (run) {
anyrun = true;
/* полный проход */
while(1) {
if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
perror("io3");
cleanExit(1);
}
file[j]->rec.key = win->key;
file[j]->valid = true;
if ((win = readRec()) == NULL) break;
if (compLT(win->key, file[j]->rec.key)) break;
}
}
}
/* Если нет места для проходов - вверх на уровень */
if (!anyrun) {
int t;
level++;
t = file[0]->fib;
for (j = 0; j <= fileP; j++) {
file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
file[j]->fib = t + file[j+1]->fib;
}
}
}
}
void rewindFile(int j) {
/* Идти в начало file[j] и читать первую запись */
file[j]->eor = false;
file[j]->eof = false;
rewind(file[j]->fp);
if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
if (feof(file[j]->fp)) {
file[j]->eor = true;
file[j]->eof = true;
} else {
perror("io5");
cleanExit(1);
}
}
}
void mergeSort(void) {
int fileT;
int fileP;
int j;
tmpFileType *tfile;
/* Многофазная сортировка слиянием */
fileT = nTmpFiles - 1;
fileP = fileT - 1;
/* снабдить файлы информацией */
for (j = 0; j dummy) {
allDummies = false;
if (!file[j]->eof) anyRuns = true;
}
}
if (anyRuns) {
int k;
keyType lastKey;
/* слить 1 проход file[0]..file[P] --> в file[T] */
while(1) {
/* Каждый проход по циклу записывает 1 запись в file[fileT]
*/
/* Hайти наименьший ключ */
k = -1;
for (j = 0; j <= fileP; j++) {
if (file[j]->eor) continue;
if (file[j]->dummy) continue;
if (k < 0 ||
(k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
k = j;
}
if (k < 0) break;
/* записать record[k] в file[fileT] */
if (fwrite(&file[k]->rec, sizeof(recType), 1,
file[fileT]->fp) != 1) {
perror("io6");
cleanExit(1);
}
/* заменить record[k] */
lastKey = file[k]->rec.key;
if (fread(&file[k]->rec, sizeof(recType), 1,
file[k]->fp) == 1) {
/* проверить на предмет конца пробега file[s] */
if (compLT(file[k]->rec.key, lastKey))
file[k]->eor = true;
} else if (feof(file[k]->fp)) {
file[k]->eof = true;
file[k]->eor = true;
} else {
perror("io7");
cleanExit(1);
}
}
/* Подкорректировкать холостые */
for (j = 0; j <= fileP; j++) {
if (file[j]->dummy) file[j]->dummy--;
if (!file[j]->eof) file[j]->eor = false;
}
} else if (allDummies) {
for (j = 0; j <= fileP; j++)
file[j]->dummy--;
file[fileT]->dummy++;
}
/* конец прохода */
if (file[fileP]->eof && !file[fileP]->dummy) {
/* completed a fibonocci-level */
level--;
if (!level) {
/* готово, file[fileT] содержит данные */
return;
}
/* fileP истощился, открываем новый такой же */
fclose(file[fileP]->fp);
if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
== NULL) {
perror("io8");
cleanExit(1);
}
file[fileP]->eof = false;
file[fileP]->eor = false;
rewindFile(fileT);
/* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
tfile = file[fileT];
memmove(file + 1, file, fileT * sizeof(tmpFileType*));
file[0] = tfile;
/* начать новые проходы */
for (j = 0; j <= fileP; j++)
if (!file[j]->eof) file[j]->eor = false;
}
}
}
}
void extSort(void) {
initTmpFiles();
makeRuns();
mergeSort();
termTmpFiles(0);
}
int main(int argc, char *argv[]) {
/* командная строка:
*
* ext ifName ofName nTmpFiles nNodes
*
* ext in.dat out.dat 5 2000
* читает in.dat, сортирует, используя 5 файлов и 2000 узлов,
* выводит в out.dat
*/
if (argc != 5) {
printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
cleanExit(1);
}
ifName = argv[1];
ofName = argv[2];
nTmpFiles = atoi(argv[3]);
nNodes = atoi(argv[4]);
printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
nTmpFiles, nNodes, sizeof(recType));
extSort();
return 0;
} |
| |
|
25.05.2003, 14:46
| #8 |
| » Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 |
вот. copy/paste-нуто из файла который не помню откуда скачал :] |
| |
|
25.05.2003, 15:41
| #10 | |
| ¡no pasaran!  Join Date: 03 2002 Location: localhost Age: 39
Posts: 540
Downloads: 0 Uploads: 0
Reputation: 13 | 4 | Quote:
 | |
| |
|
26.05.2003, 04:55
| #11 |
| Грустно...  Join Date: 08 2002 Location: Там, где всегда идут дожди Age: 38
Posts: 21,717
Downloads: 2 Uploads: 0
Reputation: 250 | 8 |
Это не Кнут - это частично КЛР (Кормен, Лейзер..., Ривест). Хотя у Кнута все это то же есть. А на самом деле это скорее всего FAQ с fido7.ru.algorithms или любой другой источник факов  ))По сути дела: Еще есть фича - в сортироке вставкой нахождения места элемента можно сделать быстрее если с самого начала проверять его на меньше/больше первого и последнего элемента, и находить позицию двоичным поиском. Правда время от этого особо не улучшится Почему?
|
| |
|
26.05.2003, 06:33
| #12 |
| Академик  Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 |
очень полезный топик, zombie.
|
| |
|
26.05.2003, 14:43
| #13 |
| Академик  Join Date: 08 2002 Location: Yerevan, Armenia Age: 49
Posts: 4,854
Downloads: 1 Uploads: 0
Reputation: 225 | 4 |
Nu, konechno, nineshnie programmisti Bibliyu ne chitayut, tak xot` tut pust` chemu-nibud` pouchatsya.
|
| |
|
27.05.2003, 17:37
| #14 |
| Banned  Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 |
jal' exameni uje zakonchilis', ya teper' sam expert vo vsem etom.. gdej ti ran'she to bil zombiiiiiiiiii? |
| |
| Sponsored Links |
 |
| Thread Tools | |
| |
| На правах рекламы: | |
 | |
