02 июня 2020 года    
Вторник | 13:09    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







Разделы / Программирование / Программные руководства

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

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

From: Ilia Kantor <Ilia.Kantor@p6.f1815.n5020.z2.fidonet.org>
Date: Fri, 26 Jan 2001 16:55:14 +0300

 Sorting FAQ V1.1

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

>             Вопросы

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

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

3. Описание и исходник InsertSort (сортировка простыми вставками).

4. Описание и исходник QuickSort (быстрая сортировка).

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

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

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

8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?

9. Что лучше: распределяющая сортировка или быстрая ?

10. Есть большой файл. Как его отсортировать ? Сортировка слиянием.


>                Ответы


====================================================================

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

====================================================================
A: Kantor Ilia - Tomas Niemann.

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

         Для оценки производительности алгоритмов можно использовать
    разные подходы. Самый бесхитростный - просто запустить каждый
    алгоритм на нескольких задачах и сравнить время исполнения. Другой
    способ - оценить время исполнения. Например, мы можем утверждать,
    что время поиска есть O(n) (читается так: о большое от n).

         Когда используют обозначение O(), имеют в виду не точное время
    исполнения, а только его предел сверху, причем с точностью до
    постоянного множителя. Когда говорят, например, что алгоритму
    требуется время порядка O(n^2), имеют в виду, что время исполнения
    задачи растет не быстрее, чем квадрат количества элементов. Чтобы
    почувствовать, что это такое, посмотрите на таблицу, где приведены
    числа, иллюстрирующие скорость роста для нескольких разных функций.

          n        log n     n*log n             n^2

      1            0       0             1

      16           4       64            256

      256          8       2,048         65,536

      4,096        12      49,152        16,777,216

      65,536       16      1,048,565     4,294,967,296

      1,048,476    20      20,969,520    1,099,301,922,576

      16,775,616   24      402,614,784   281,421,292,179,456

         Если считать, что числа в таблице соответствуют микросекундам,
    то для задачи с 1048476 элементами алгоритму с временем работы
    O(log n) потребуется 20 микросекунд, а алгоритму с временем работы
    O(n^2) - более 12 дней.

>     Если оба алгоритма, например, O ( n*log n ), то это отнюдь
>    не значит, что они одинакого эффективны.

    Символ О не учитывает константу, то есть первый может быть, скажем
    в 1000 раз эффективнее. Это значит лишь то, что их время возрастает
    приблизительно как функция n*log n.

>    За функцию берется количество операций, возрастающее быстрее всего.

    То есть если в программе одна функция выполняется O(n) раз -
    например, умножение, а сложение - O(n^2) раз, то общая сложность -
    O(n^2), так как в конце концов при увеличении n более быстрые ( в
    определенное, константное число раз ) сложения станут выполнятся
    настолько часто, что будут тормозить куда больше, нежели медленные,
    но редкие умножения.

>    Основание логарифма не пишется.

    Причина этого весьма проста. Пусть у нас есть O(log2_n). Но log2_n =
    log3_n / log3_2, а log3_2, как и любую константу, асимптотика - символ
    О() не учитывает. Таким образом, O(log2_n) = O( log3_n).
    К любому основанию мы можем перейти аналогично, а, значит, и писать
    его не имеет смысла.


====================================================================

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

====================================================================
A: Kantor Ilia

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

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


====================================================================

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

====================================================================
A: Kantor Ilia - Nicolas Virt - Tomas Niemann ;-))

                                 Алгоритм

             Все элементы условно разделяются на готовую
        последовательность a1 ... ai-1 и входную ai ... an. На
        каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й
        элемент входной последовательности и вставляем его на
        нужное место в готовую.

             Пример:

        Начальные ключи         44 \\ 55 12 42 94 18 06 67
                 i = 2          44 55 \\ 12 42 94 18 06 67
                 i = 3          12 44 55 \\ 42 94 18 06 67
                 i = 4          12 42 44 55 \\ 94 18 06 67
                 i = 5          12 42 44 55 94 \\ 18 06 67
                 i = 6          12 18 42 44 55 94 \\ 06 67
                 i = 7          06 12 18 42 44 55 94 \\ 67
                 i = 8          06 12 18 42 44 55 67 94 \\

             При поиске подходящего места удобно 'просеивать' x,
        сравнивая его с очередным элементом ai и либо вставляя его,
        либо пересылая ai направо и продвигаясь налево.

             Просеивание может кончиться при двух условиях:

             1. Найден ai с ключом, меньшим x.

             2. Достигнут конец готовой последовательности.

             Метод хорош устойчивостью сортировки, удобством для
        реализации в списках и, самое главное, естественностью
        поведения. То есть уже частично отсортированный массив
        будут досортирован им гораздо быстрее чем многими
        'продвинутыми' методами.

                                  Анализ

        Число сравнений
                             минимальное:           n - 1
                             среднее:         ( n^2 + n - 2 ) / 4
                             максимальное:   ( n^2 + n ) * / 2 - 1
        Количество пересылок
                             минимальное:       2 * ( n - 1 )

                             среднее:      ( n^2 + 9 * n - 10 ) / 4

                             максимальное:  ( n^2 + 3 * n - 4 ) / 2

        Пример на Си - Tomas Niemann.
--------------------------------------------------------------------
typedef int item;          /* Тип сортируемых элементов */
typedef int tblIndex;      /* Тип ключей, по которым сортируем */

#define compGT(a,b) (a > b)   /* Функция сравнения  */

void insertSort(T *a, tblIndex lb, tblIndex ub) {
    item t;
    tblIndex i, j;

   /***********************
    * сортируем a[lb..ub] *
    ***********************/
    for (i = lb + 1; i <= ub; i++) {
        t = a[i];

        /* Сдвигаем элементы вниз, пока */
        /*  не найдем место вставки.    */
        for (j = i-1; j >= lb && compGT(a[j], t); j--)
            a[j+1] = a[j];

        /* вставка */
        a[j+1] = t;
    }
}


====================================================================

> 4. Описание и исходник QuickSort (быстрая сортировка).

====================================================================

                             Основной алгоритм

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

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

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

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

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

 Пример рекурсивной QuickSort
------------------------------------
typedef int item;       /* Тип сортируемых элементов */
typedef int tblIndex;   /* Тип ключей, по которым сортируем */

#define CompGT(a,b) (a > b)

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
     item t, pivot;
    tblIndex i, j, p;

   /**********************************
    *  разделение массива a[lb..ub]  *
    **********************************/

    /* Выбираем центр - pivot */
    p = lb + ((ub - lb)>>1);
    pivot = a[p];
    a[p] = a[lb];

    /* сортируем lb+1..ub относительно центра */
    i = lb+1;
    j = ub;
    while (1) {
        while (i < j && compGT(pivot, a[i])) i++;
        while (j >= i && compGT(a[j], pivot)) j--;
        if (i >= j) break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        j--; i++;
    }

    /* центр в a[j] */
    a[lb] = a[j];
    a[j] = pivot;

    return j;
}

void quickSort(T *a, tblIndex lb, tblIndex ub) {
    tblIndex m;

   /**************************
    *  сортируем  a[lb..ub]  *
    **************************/

    while (lb < ub) {

        /* сортировка вставками для малых массивов */
        if (ub - lb <= 12) {
            insertSort(a, lb, ub);
            return;
        }

        /* разделение пополам */
        m = partition (a, lb, ub);

        /* Уменьшаем требования к памяти:    */
        /*  меньший сегмент сортируем первым */
        if (m - lb <= ub - m) {
            quickSort(a, lb, m - 1);
            lb = m + 1;
        } else {
            quickSort(a, m + 1, ub);
            ub = m - 1;
        }
    }
}

                                 Улучшения

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

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

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


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

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

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

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

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

#include <limits.h>
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)

static void exchange(void *a, void *b, size_t size) {
    size_t i;

    /******************
     *  обменять a,b  *
     ******************/

    for (i = sizeof(int); i <= size; i += sizeof(int)) {
        int t = *((int *)a);
        *(((int *)a)++) = *((int *)b);
        *(((int *)b)++) = t;
    }
    for (i = i - sizeof(int) + 1; i <= size; i++) {
        char t = *((char *)a);
        *(((char *)a)++) = *((char *)b);
        *(((char *)b)++) = t;
    }
}

void qsort(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *)) {
    void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
    int sp;
    unsigned int offset;

    lbStack[0] = (char *)base;
    ubStack[0] = (char *)base + (nmemb-1)*size;
    for (sp = 0; sp >= 0; sp--) {
        char *lb, *ub, *m;
        char *P, *i, *j;

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

        while (lb < ub) {

            /* выбираем центр и меняемся с 1м элементом */
            offset = (ub - lb) >> 1;
            P = lb + offset - offset % size;
            exchange (lb, P, size);

            /* разделение в два сегмента */
            i = lb + size;
            j = ub;
            while (1) {
                while (i < j && compar(lb, i) > 0) i += size;
                while (j >= i && compar(j, lb) > 0) j -= size;
                if (i >= j) break;
                exchange (i, j, size);
                j -= size;
                i += size;
            }

            /* центр в A[j] */
            exchange (lb, j, size);
            m = j;

            /* Меньший сегмент продолжаем обрабатывать, больший - в стек */
            if (m - lb <= ub - m) {
                if (m + size < ub) {
                    lbStack[sp] = m + size;
                    ubStack[sp++] = ub;
                }
                ub = m - size;
            } else {
                if (m - size > lb) {
                    lbStack[sp] = lb;
                    ubStack[sp++] = m - size;
                }
                lb = m + size;
            }
        }
    }
}


====================================================================

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

====================================================================

A: Kantor Ilia - Nicolas Virt

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

                           hl , hl+1 , ... , hr

     такую, что
                                 hi <= h2i

                                hi <= h2i+1

     для всякого i = l , ... , r/2

          Геометрическая интерпретация пиромиды:

                      h1
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
               h2            h3
              / \            / \
             /   \          /   \
           h4    h5       h6     h7
          /  \  /  \     / \   /  \
         h8  h9 h10 h11  h12 h13 h14 h15

      Для последовательности 06 42 12 55 94 18 44

                      06
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
               42            12
              / \            / \
             /   \          /   \
           55    94        18   44

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

          1. Новый элемент Х помещаем в вершину дерева.

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

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

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

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

          На каждом шаге добавляется новый элемент слева и
     'просеивается' на место. Вот иллюстрация процесса для пирамиды
     из 8-и элементов:

     44  55  12  42  //  94  18  06  67
     44  55  12  //  42  94  18  06  67
     44  55  //  06  42  94  18  12  67
     44  //  42  06  55  94  18  12  67
     //  06  42  12  55  94  18  44  67

                            Фаза 2: сортировка

          Для того, чтобы рассортировать элементы, необходимо
     выполнить n шагов просеивания: после каждого шага очередной
     элемент берется с вершины пирамиды. На каждом шаге берем
     последний элемент Х, верхний элемент пирамиды помещается на его
     место, а Х просеивается на свое 'законное'. В этом случае
     необходимо совершить n - 1 шагов. Пример:

      06  42  12  55  94  18  44  67  //
      12  42  18  55  94  67  44  //  06
      18  42  44  55  94  67  //  12  06
      42  55  44  67  94  //  18  12  06
      44  55  94  67  //  42  18  12  06
      55  67  94  //  44  42  18  12  06
      67  94  //  55  44  42  18  12  06
      94  //  67  55  44  42  18  12  06


          Ну вот мы м получили отсортированную последовательность,
     только в обратном порядке. Изменяя сравнения на
     противоположные, получаем функцию Heapsort на Паскале

          Прекрасной характеристикой этого метода является то, что
     среднее число пересылок - (n*log n)/2 и отклонения от этого
     значения сравнительно малы.


{ сортируем массив типа 'item' по ключу 'a.key' }

procedure Heapsort;
 var i,l: index; x: item;

procedure sift;
 label 13;
 var i, j: index;
begin i := l; j := 2*i; x := a[i];
 while j <= r do
 begin if j < r then
  if a[j].key < a[j+1].key then j := j+1;
  if x.key >= a[j].key then goto 13;
  a[i] := a[j]; i := j; j := 2*i
 end;
 13: a[i] := x
 end;

 begin l := (n div 2) + 1; r := n;
  while l > 1 do
   begin l := l - 1; sift
   end;

  while r > 1 do
   begin x := a[l]; a[l] := a[r]; a[r] := x;
     r := r - 1; sift
 end
end { heapsort }

==============================================================

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

==============================================================
A: Kantor Ilia

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

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

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

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

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

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

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

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


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

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

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

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

====================================================================

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

====================================================================
A: Kantor Ilia

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

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

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

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

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

  Вообще, нужно смотреть по данным и имеющимся в наличии ресурсам,
 но в типичных случаях наибыстрейшими решениями станут <см выше>.


===========================================================================

> 8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка
> ?

===========================================================================
A: Kantor Ilia

  К сожалению, или к счастью, единица информации в современной технике
 способна применять лишь 2 значения: 1 и 0.
  А значит, любые компьютерные данные тоже могут принимать ограниченное
 количество значений, так как состоят из некоторого числа битов ;-)).


  Пусть имеем максимум по k байт в каждом ключе ( хотя, за элемент
 сортировки вполне можно принять и что-либо другое. k должно быть
 известно заранее, до сортировки.

 Разрядность данных ( количество возможных значений элементов k) - m.

  Если мы сортируем слова, то элемент сортировки - буква. m = 33.
 Если в самом длинном слове 10 букв, k = 10.

   Обычно мы будем сортировать данные по ключам из k байт, m=255.

----------------------------------------------------------------------
   Пусть у нас есть массив source из n элементов по одному байту в каждом.

 Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 },
и проделать с ним все операции, имея в виду m=9.

     I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и
заполняться она будет так:

for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;

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

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

int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];

     В index[i] мы поместили информацию о будущем количестве символов в
отсортированном массиве до символа с ключом i.
     Например, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.

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

for ( i = 0; i < n ; i++ )
     {
      sorted[ index[ source[i] ] ]=source[i];
// попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
      index[ source[i] ] = index[ source[i] ] +1;
     }

     Итак, мы научились за O ( n ) сортировать байты. А от байтов до строк
и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

  Будем действовать в десятичной системе и сортировать обычные числа
 ( m = 10 ).

      сначала они в        сортируем по младшему     на один
       беспорядке:               разряду:             выше:     и еще раз:
           523                      523                523         088
           153                      153                235         153
           088                      554                153         235
           554                      235                554         523
           235                      088                088         554

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

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

 #include <iostream.h>
 #include < stdlib.h>
 #include < string.h>

 void radix (int byte, long N, long *source, long *dest)
 {
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for(i=0;i<N;i++) dest[index[((source[i])>>(byte*8))&0xff]++]=source[i];
 }

 void radixsort (long *source, long *temp, long N)
 {
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
 }

 void make_random (long *data, long N)
 {
  for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
 }

 long data[10000];
 long temp[10000];

 void main (void)
 {
  make_random(data, 10000);
  radixsort (data, temp, 10000);
  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
 }


===========================================================================

> 9. Что быстрее: распределяющая сортировка или QuickSort ?

===========================================================================
A: Kantor Ilia

   Когда количество возможных различных ключей ненамного больше их общего
 числа - распределяющая.

  Различных ключей очень много, размер массива сравнительно небольшой
      - быстрая.


===========================================================================

> 10. Есть большой файл. Как его отсортировать ?

===========================================================================
A: Kantor Ilia - Tomas Niemann

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

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

 Пример для 3-х серий, слияемых на 4-ю:

    3 7 9      3 7 9        3 7 9          7 9             7 9
  { 2 4 6  1 { 2 4 6  1 2 { 4 6    1 2 3 { 4 6   1 2 3 4 { 6
    1 5 8      5 8          5 8            5 8             5 8

               7 9                7 9                 9
   1 2 3 4 5 { 6    1 2 3 4 5 6 { 8     1 2 3 5 6 7 { 8   1 2 3 4 5 6 7 8 9 {
               8

   Каждый pаз мы беpем свеpху наименьший элемент.
      Таким образом, каждая операция слияния серий требует n пересылок
 элементов, где n - общее число элементов серий.

      Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем
 слиять элементы со входных лент на выходную, пока какая-либо из них не
 опустеет. Затем она станет входной.

      Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии
 обозначены буквами fi, в таблице - количество элементов.

    Тип     f1      f2     f3     f4     f5      f6

            16      15     14     12     8
            8       7      6      4      0       8
            4       3      2      0      4       4
            2       1      0      2      2       2
            1       0      1      1      1       1
            0       1      0      0      0       0

      В каждый момент времени слияние происходит на пустую ленту с остальных,
 поэтому число требующихся проходов приблизительно равно log N n. В данном
 примере распределение начальных серий побрано искусственно. Для идеальной
 сортировки исходные числа серий должны быть суммами n - 1 , n - 2 , ... , 1
 последовательных чисел Фибоначчи порядка n - 2.

      Число Фибоначчи порядка p определяются следующим образом:
 fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p,
 fp(p) = 1,
 fi(p) = 0 для 0 <= i < p.
      Очевидно, обычные числа Фибоначчи имеют порядок 1.

      Поэтому предположим существование фиктивных серий, таких что сумма
 фиктивных с реальными дает идеальное число.

      Сначала все данные располагаются на одной ленте. Лента читается и
 отрезки распределяются по другим лентам, имеющимся в системе. после того,
 как созданы начальные отрезки, они сливаются, как описано выше. Один из
 методов, который можно использовать для создания начальных отрезков, состоит
 в чтении порции записей в память, их сортировке и записи результата на
 ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот
 алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала
 мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут
 исчерпаны входные данные:

    * Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >=
      значения ключа последней прочитанной записи.
    * Если все "старые" ключи меньше последнего ключа, то мы достигли конца
      отрезка. Выбираем запись с наименьшим ключом в качестве первого
      элемента следующего отрезка.
    * Записываем выбранную запись.
    * Заменяем выбранную и записанную запись на новую из входного файла.

      На следующей таблице выбор с замещением иллюстрируются для совсем
 маленького файла.

      Начало файла - справа. Чтобы упростить пример, считается, что в буфер
 помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер
 помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в
 выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась
 запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла -
 с ключом 4. Процесс продолжается до шага F,  где мы оказывается, что
 последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы
 заканчиваем формирование текущего отрезка и начинаем формирование
 следующего.

                      Шаг    Вход     Буфер     Выход
                       A  5-3-4-8-6-7
                       B  5-3-4-8     6-7
                       C  5-3-4       8-7   6
                       D  5-3         8-4   7-6
                       E  5           3-4   8-7-6
                       F              5-4   3 | 8-7-6
                       G              5     4-3 | 8-7-6
                       H                    5-4-3 | 8-7-6

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

 Прочитав из входного файла очередную запись, мы ищем наименьший ключ,
 который >= последнего считанного. При этом мы, конечно, можем просто
 сканировать записи в буфере. Однако, если таких записей тысячи, время поиска
 может оказаться недопустимо большим. Если на этом этапе использовать
 двоичные деревья, нам понадобится всего лишь log n сравнений.

                                  Реализация

 В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec
 для чтения очередной записи. В функции readRec используется выбор с
 замещением (с двоичными деревьями) для получения нужной записи, а makeRuns
 распределяет записи согласно ряду Фибоначчи. Если количество отрезков
 оказывается вне последовательности Фибоначчи, в начало каждого файла
 добавляются пустые отрезки. Затем вызывается функция mergeSort, которая
 производит многофазное слияние отрезков.

-----------------------------------------------------------

/* внешняя сортировка */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* темплейт для временных файлов (формат 8.3) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* операторы сравнения */
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y)

/* определяем сортируемые записи */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
    keyType key;                         /* ключ, по которому сортируем */
    #if LRECL
        char data[LRECL-sizeof(keyType)];       /* остальные поля */
    #endif
} recType;

typedef enum {false, true} bool;

typedef struct tmpFileTag {
    FILE *fp;                   /* указатель на файл */
    char name[LNAME];           /* имя файла */
    recType rec;                /* последняя прочитанная запись */
    int dummy;                  /* номер холостых проходов */
    bool eof;                   /* флаг конца пробега end-of-file */
    bool eor;                   /* флаг конца прохода end-of-run */
    bool valid;                 /* верно, если запись - годная */
    int fib;                    /* идеальное число Фибоначчи */

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

 FAQ по СОРТИРОВКАМ.
Лента новостей


2006 (c) Copyright Hardline.ru