Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11656
Последний выпуск: 19.06.2015

FAQ по СОРТИРОВКАМ версия 1.1

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


A: Kantor Ilia - Tomas Niemann
Оценки времени исполнения. 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). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла.

2. Какие на сегодняшний день самые эффективные методы сортировки?

A: Kantor Ilia

быстрая сортировка, распределяющая сортировка и быстрая сортировка с составными ключами, которая слишком сложна для ФАКа.

Для прикладных задач, использующих элементы сортировки также очень полезна пирамидальная сортировка.

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

A: Kantor Ilia - Nicolas Virt - Tomas Niemann ;-)) Алгоритм

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

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 = 0; sp--) {
        char *lb, *ub, *m;
        char *P, *i, *j;

        lb = lbStack[sp];
        ub = ubStack[sp];

        while (lb > 1;
            P = lb + offset - offset % size;
            exchange (lb, P, size);

            /* разделение в два сегмента */
            i = lb + size;
            j = ub;
            while (1) {
                while (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  lb) {
                    lbStack[sp] = lb;
                    ubStack[sp++] = m - size;
                }
                lb = m + size;
            }
        }
    }
}

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

A: Kantor Ilia - Nicolas Virt

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

  hl , hl+1 , ... , hr
     такую, что
  hi 

Добавление элемента в готовую пирамиду

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 = 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 раза медленнее быстрой. Hаихудшего случая нет - всегда O(nlogn). Практически, ее элементы часто применяются в смежных задачах.

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

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

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

A: Kantor Ilia

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

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

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

Для сортировок распределением это - 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 

Для нашего примера будем иметь distr = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }, то есть i-ый элемент distr[] - количество ключей со значением i.

     Заполним таблицу индексов:

int index[256];
index [0]=0;
for ( i = 1 ; i 

В index[i] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i.

Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.

     А теперь заполняем новосозданный массив sorted размера n:

for ( i = 0; i 

Hу вот мы и отсортировали за O ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'!

Реализация на C++ для long int'ов. Сам не делал - валялась в и-нете.

 #include 
 #include 
 #include 

 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>(byte*8))&0xff]++;
  index[0]=0;
  for ( i=1; 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 

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 

Очевидно, обычные числа Фибоначчи имеют порядок 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 "_sort%03d.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 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 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 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 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 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 eor) continue;
                        if (file[j]->dummy) continue;
                        if (k rec.key, file[j]->rec.key)))
                            k = j;
                    }
                    if (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 dummy) file[j]->dummy--;
                    if (!file[j]->eof) file[j]->eor = false;
                }

            } else if (allDummies) {
                for (j = 0; 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] 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;
}

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог