Faq по СОРТИРОВКАМ

[z0mbie]

Ликбез для понимания важной информации: Что означает символ O(n)? Почему не пишется основание логарифма: O (log n)?

Оценки времени исполнения. Cимвол O().

Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Hапример, мы можем утверждать, что время поиска есть 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). Hо log2_n = log3_n / log3_2, а log3_2, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O(log2_n) = O( log3_n). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла.

[z0mbie]

Сортировка простыми вставками.


Все элементы условно разделяются на готовую последовательность 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;
    }
}

[z0mbie]

Описание QuickSort (быстрая сортировка).
Основной алгоритм

Выберем случайным образом какой-то элемент с у просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший У. Поменяем их местами и продолжим процесс просмотра с обменом, пока просмотры не встретятся где-то в середине массива.

В результате массив разделится на две части: левую - с ключами, меньшими с у ночаяв - с ключами, большими У.

Этот шаг называется разделением. у - центром.

К получившимся частям рекурсивно применяем ту же процедуру.

В результате получается очень эффективная сортировка


Улучшения


Hа практике для увеличения быстроты, но не
асимптотики, можно произвести несколько улучшений:


1. В качестве центрального для функции partition
выбирается элемент, расположенный в середине. Такой
выбор улучшает оценку среднего времени работы, если
массив упорядочен лишь частично. Hаихудшая для этой
реализации ситуация возникает в случае, когда каждый
раз при работе partition в качестве центрального
выбирается максимальный или минимальный элемент.


1' Можно выбрать средний из первого, последнего и среднего элементов.
Maxim Razin: Тогда количество проходов уменьшится в 7/6 раз.


2. Для коротких массивов вызывается сортировка
вставками. Из-за рекурсии и других "накладных
расходов" быстрый поиск оказывается не столь уж
быстрым для коротких массивов. Поэтому, если в массиве
меньше 12 элементов, вызывается сортировка вставками.
Пороговое значение не критично - оно сильно зависит от
качества генерируемого кода.


3. Если последний оператор функции является
вызовом этой функции, говорят о хвостовой рекурсии. Ее
имеет смысл заменять на итерации - в этом случае лучше
используется стек.


4. После разбиения сначала сортируется меньший
раздел. Это также приводит к лучшему использованию
стека, поскольку короткие разделы сортируются быстрее
и им нужен более короткий стек. Требования к памяти
уменьшаются с n до log n.


Пример, входящий в стандартную реализацию Си
использует многие из этих улучшений.

Стандартная реализация итерационной QuickSort

------------------------------------------------
#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;
            }
        }
    }
}

[z0mbie]

Описание и исходник HeapSort (пирамидальная сортировка).



Hазовем пирамидой последовательность элементов

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. Hовый элемент у помещаем в вершину дерева.


2. Смотрим на элемент слева и элемент справа - выбираем наименьший.


3. Если этот элемент меньше у - меняем их местами и идем у шагу 2. Иначе конец процедуры.


Фаза 1: построение пирамиды


Пусть дан массив h1 ... hn . Ясно, что элементы hn/2 + 1
... hn уже образуют 'нижний ряд' пирамиды, так как не
существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То
есть тут упорядочивания не требуется.


Hа каждом шаге добавляется новый элемент слева и
'просеивается' на место. Вот иллюстрация процесса для пирамиды
из 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 шагов просеивания: после каждого шага очередной
элемент берется с вершины пирамиды. Hа каждом шаге берем
последний элемент у, верхний элемент пирамиды помещается на его
место, а у просеивается на свое 'законное'. В этом случае
необходимо совершить 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

Hу вот мы и получили отсортированную последовательность,
только в обратном порядке. Изменяя сравнения на
противоположные, получаем функцию 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 }

[z0mbie]

Требования QuickSort и HeapSort. InsertSort... Что лучше?


Простые вставки.



Общее быстродействие - O( n^2 ), но ввиду простоты метода,
является наибыстрейшим для малых ( 12-20 элементов ) массивов.


Естественное поведение. Легко прибавлять новые элементы.
Ввиду своих особенностей, чрезвычайно хорош для списков.


Сортировка не требует дополнительной памяти.

Быстрая сортировка



Общее быстродействие - O( nlogn ). Случай n^2 теоретически
возможен, но крайне [ 1 / (n^logn) ] маловероятен.


В общем и целом - наиболее быстрая сортировка сравнениями
для разупорядоченных массивов с >50 элементами.


Поведение неестественно. Уже практически отсортированный
массив будет сортироваться столько же, сколько и полностью
разупорядоченный.


Итерационный вариант требует logn памяти, рекурсивный - O(n).

Пирамидальная сортировка.



В 1.5 раза медленнее быстрой. Hаихудшего случая нет -
всегда O(nlogn). Практически, ее элементы часто применяются в
смежных задачах.


Поведение неестественно.


Основное достоинство - сортировка не требует дополнительной памяти.

[z0mbie]

Какая самая быстрая сортировка?



Давайте разберемся раз и навсегда. Есть два типа сортировок:

 Распределяющая и ее вариации        |       Сортировка сравнениями
                                     |
Основана на том, что число возможных |   Пользуется лишь возможностью
 значений ключа конечно.             |     прямого сравнения ключей и
                                     |        их упорядоченностью.
                                     |    Quicksort, Heapsort...

Для сортировок сравнениями давно доказана теорема
о максимальном быстродействии: O(nlog n).


Для сортировок распределением это - O(n). Быстрее сортировать нельзя.

Итак, наибыстрейшие сортировки -
Quicksort - быстрая,
Radix sort - распределяющая
и их молодой гибрид:
Multiway Quicksort /MQS / - быстрая с составными ключами.
например, для строк.

[z0mbie]

Многофазная сортировка


Этот тип сортировки относится к так называемым 'сортировкам слиянием'.
Слиянием называется процесс объединения нескольких упорядоченных серий в
одну.

Пример для 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, в таблице - количество элементов.

    Тип     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. В этот момент мы
заканчиваем формирование текущего отрезка и начинаем формирование
следующего.

                      Шаг    Вход     Буфер     Выход
                       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 
#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;
}

[z0mbie]

вот.
copy/paste-нуто из файла который не помню откуда скачал :]

[acid]

Спасибо z0mbie, думаю многим это будет полезно.

[dolphin]

Originally posted by z0mbie
вот.
copy/paste-нуто из файла который не помню откуда скачал :]

кажется это из Д.Кнута. Но почему примеры на С не знаю

[Agregat]

Это не Кнут - это частично КЛР (Кормен, Лейзер..., Ривест). Хотя у Кнута все это то же есть.
А на самом деле это скорее всего FAQ с fido7.ru.algorithms или любой другой источник факов ))

По сути дела:
Еще есть фича - в сортироке вставкой нахождения места элемента можно сделать быстрее если с самого начала проверять его на меньше/больше первого и последнего элемента, и находить позицию двоичным поиском.
Правда время от этого особо не улучшится Почему?

[greka]

очень полезный топик, zombie.

[W_z_rd]

Nu, konechno, nineshnie programmisti Bibliyu ne chitayut, tak xot` tut pust` chemu-nibud` pouchatsya.

[DaNYer]

jal' exameni uje zakonchilis', ya teper' sam expert vo vsem etom..

gdej ti ran'she to bil zombiiiiiiiiii?