ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/1815.6  19 Mar 2002  17:47:36
 To : All
 Subject : S0rting FAQ 1/4
 -------------------------------------------------------------------------------- 
 

 
 === Cut ===
 
  S0rting FAQ v2.21
 
             FAQ   по  СОРТИРОВКАМ версия от 15.02.2002
 
     В процессе работы над FAQом я смотрел многие источники
 по этим вопросам, в которых(даже написанных самыми уважаемыми авторами)
 зачастую давались разные, иногда противоречивые сведения.
 Особенно это касается характеристик сортировок.
 
    В FAQ были включены те, которые я счел правильными.
 Однако 'субъективных' оценок алгоритмов не бывает, поэтому по
 всем вопросам, вызывающим _аргументированные_ сомнения,
 пишите мне на адреса:
 
                                                Ilia Kantor
                                  email: <algolist@mail.ru>
                                Fido: 2:5020/1815.6@FidoNet
                                 web: http://algolist.da.ru
 
 >             Вопросы
 
 1.  Ликбез для понимания важной информации:
  Что означает символ O(n) ? Оценки Omega() и Theta()
  Почему _не пишется_ основание логарифма: O(logn) ?
 
 2. Какие на сегодняшний день самые эффективные методы сортировки ?
 
 3. Описание и исходник SelectSort (сортировка выбором).
 
 4. Сортировка пузырьком BubbleSort и ее улучшения с исходниками.
 
 5. Описание и исходник InsertSort (сортировка простыми вставками).
 
 6. Описание и исходник ShellSort (сортировка Шелла).
 
 7. Описание и исходник сортировки двоичным деревом
    (TreeSort, 'древесная сортировка'). Выбор с замещением.
 
 8. Описание и исходник QuickSort (быстрая сортировка).
 
 9. Описание и исходник HeapSort (пирамидальная сортировка).
 
 10. Описание MergeSort (сортировка слиянием).
 
 11. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?
 
 12. Требования и свойства сортировок. Что когда лучше?
    12.1 Какая самая быстрая сортировка ?
    12.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?
 
 13. Есть большой файл. Как его отсортировать ? Многофазное слияние.
 
 App. Использованная литература.
 
 >                Ответы
 ====================================================================
 
 > 1.  Ликбез для понимания важной информации:
 >    Что означает символ O(n) ? Оценки Omega() и Theta()
 >    Почему _не пишется_ основание логарифма: O(logn) ?
 
 ====================================================================
 
                   Оценки времени исполнения. Cимвол O().
 
          Для оценки производительности алгоритмов можно использовать
     разные подходы. Самый бесхитростный - просто запустить каждый
     алгоритм на нескольких задачах и сравнить время исполнения. Другой
     способ - оценить время исполнения через символ O(n) (читается так:
     о большое от n). 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 раз эффективнее. Это значит лишь то, что время (или требуемая
     память или что-либо еще, что надо оценить) возрастает приблизительно
     c такой же скоростью, как функция n*log n.
 
 >    За функцию берется количество операций, возрастающее быстрее всего.
 
       То есть если в программе одна функция выполняется O(n) раз -
     например, умножение, а сложение - O(n^2) раз, то общая сложность -
     O(n^2), так как n^2 возрастает быстрее.
       Практический смысл этого в нашем случае такой: при увеличении n
     более быстрые ( в определенное, константное число раз ) сложения
     станут выполнятся настолько часто, что будут влиять на производительность
     много сильнее, нежели медленные, но редкие умножения.
 
 >    Основание логарифма не пишется.
 
     Причина этого весьма проста. Пусть у нас есть
        O( log n ). Перейдем к основанию 3: log n = log n / log 2.
              2                                2       3       3
         Hо 1/log 2, как и любую константу, асимптотика - символ O()
                 3
     не учитывает. Таким образом, O(log n) = O(log n).
                                       2          3
     К любому основанию мы можем перейти аналогично, а, значит, и писать
     его не имеет смысла.
 
     В заключение, привожу формальную трактовку обозначения O(g(n)) для
    положительных функций f(n), g(n):
 
     Опp.1 O(g(n)) - множество функций f(n), для котоpых существуют
           положительные константы c, n0, такие что
                f(n) <= c*g(n) для всех n>=n0
 
     Опp.2 Запись f(n) = O(g(n)) означает, что f(n) - элемент множества
           O(g(n))
 
     Иногда символ O() используют в более широком смысле, подразумевая не
     только верхнюю, но и нижнюю оценку Theta(): существуют c1, c2, n0 > 0:
            0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0
 
     Кроме символа O() используются также оценки
 
         Omega(g(n)) - нижняя оценка: множество f(n): существуют c, n0>0:
       c*g(n) <= f(n)
 
         Theta(g(n)) - комбинация O() и Omega(): точная оценка асимптотики.
        Theta(g(n) - множество f(n): существуют c1, c2, n0>0:
            0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0
 
     Все описанные свойства оценки O() также верны для Omega() и Theta().
 
     Интуитивный смысл оценок:
      f = O(g) - f растет не быстрее g         }
      f = Omega(g) - f растет не медленнее g   } при n->00
      f = Theta(g) - f растет так же, как g    }
 ====================================================================
 
 > 2. Какие на сегодняшний день самые эффективные методы сортировки ?
 
 ====================================================================
 
  Быстрая сортировка, распределяющая сортировка и соpтиpовка слиянием.
 
     Для прикладных задач, использующих элементы сортировки, также
  очень полезна пирамидальная сортировка.
 
  Сpавнительные хаpактеpистики методов более подробно
  описаны в соответствующем вопpосе.
 
 ====================================================================
 
 > 3. Сортировка выбором.
 
 ====================================================================
 
      A[1..N] -  сортируемый массив из n элементов.
 
      for ( i=1; i<N; i++)
           Hайти наименьший из элементов i..N и поменять его местами с i-м.
 
      Пример действий для случайного массива A[1..8]
 
           44  55  12  42  94  18  06  67      исходный массив
      i=1  06| 55  12  42  94  18  44  67       06 <-> 44
      i=2  06  12| 55  42  94  18  44  67       12 <-> 55
      i=3  06  12  18| 42  94  55  44  67       18 <-> 55
      i=4  06  12  18  42| 94  55  44  67       42 <-> 42
      i=5  06  12  18  42  44| 55  94  67       44 <-> 94
      i=6  06  12  18  42  44  55| 94  67       55 <-> 55
      i=7  06  12  18  42  44  55  67| 94       67 <-> 94
 
        Вертикальной чертой отмечена граница уже отсортированной части
      массива.
 
      Сортировка выбором - простейший алгоритм, на практике не
    используемый ввиду низкого быстродействия. Вместо этого
    применяют ее улучшение - пирамидальную сортировку (Heapsort),
    описанную в другом вопросе, а также (иногда) 'древесную сортировку'
    (TreeSort).
 
         Пример на Паскале - Hиколас Вирт.
 --------------------------------------------------------------------
  { Сортируются записи типа item по ключу item.key }
  { для вспомогательных переменных используется тип index }
 
  procedure SelectSort;
      var i, j, k: index; x:item;
  begin for i:=1 to n-1 do
      begin k:=i; x:=a[i];
       for j:=i+1 to n do
        if a[j].key < x.key then
     begin k:=j; x:=a[j];
     end;
    a[k]:=a[i]; a[i]:=x;
   end;
  end;
 
 ====================================================================
 
 > 4. Сортировка пузырьком(BubbleSort) и ее улучшения.
 
 ====================================================================
 
   Операция сравнения/перестановки выполняется для каждых двух стоящих
 рядом элементов. После первого прохода по массиву "вверху" оказывается
 самый "легкий" элемент. Следующий цикл сортировки выполняется начиная
 со второго элемента, в результате чего вторым в массиве оказывается
 второй наименьший по величине элемент, и так далее.
 
 { Сортируются записи типа item по ключу item.key }
 { для вспомогательных переменных используется тип index }
 procedure BubbleSort;
     var i,j: index; x:item;
 begin for i:=2 to n do
     begin for j:=n downto i do
      if a[j-1].key > a[j].key then
   begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
   end;
  end;
 end;
 
   Пример 1. Проходим по массиву снизу вверх. Меньшие/более легкие/
             элементы 'всплывают' наверх, давая название методу.
 
   Hачальные  i      i      i      i      i      i      i
     ключи    2      3      4      5      6      7      8
      44 /-> 06     06     06     06     06     06     06
      55 |   44 /-> 12     12     12     12     12     12
      12 |   55 |   44 /-> 18     18     18     18     18
      42 |   12-/   55 |   44 /-> 42     42     42     42
      94 |   42 /-> 18-/   55 |   44 --> 44     44     44
      18 |   94 |   42     42-/   55     55 --> 55     55
      06-/   18-/   94 ->  67     67     67     67 --> 67
      67     67     67-/   94     94     94     94     94
 
  Алгоритм пузырька очень медленен и неэффективен. Тем не менее,
 у него есть громадный плюс: он прост и его можно по-всякому улучшать.
 Чем мы сейчас и займемся.
 
    Посмотрите на пример 1. Три последних прохода никак не влияют на
 порядок элементов, поскольку те уже отсортированы. Очевидный способ улучшить
 алгоритм - запоминать, производился ли на данном проходе какой-либо обмен.
 Если нет - это означает, что алгоритм может закончить работу.
 
    Этот процесс улучшения можно продолжить, если запоминать не столько
 сам файт обмена, но и место (индекс) последнего обмена. Ведь ясно, что
 все пары соседих элементов с индексами, меньшими этого индекса k,
 уже расположены в нужном порядке. Поэтому следующие прозоды можно заканчивать
 на этом индексе, вместо того чтобы двигаться до установленной заранее
 нижней границы i.
 
     Пойдем дальше: внимательный человек легко может заметить странную
 асимметрию: один неправильно расположенный 'пузырек' в 'тяжелом'
 конце рассортированного массива всплывет за один проход, а неправильно
 расположенный элемент в легком конце будет опускаться на правильное
 место только на один шаг при каждом проходе.
 
   Hапример, массив 12 18 42 44 55 67 94 06 будет отсортирован за 1 проход,
 а сортировка массива 94 06 12 18 42 44 55 67 потребует 7 проходов.
 
 Эта неестественная асимметрия подсказывает третье улучшение:
 менять направление следующих один за другим проходов.
 Получившийся алгоритм иногда называют 'шейкер-сортировкой'.
 
   Пример его работы на том же входном массиве.
 
          l  =  2       3       3       4       4
          r  =  8       8       7       7       4
               44  /-> 06      06      06      06
               55  |   44      44  /-> 12      12
               12  |   55 -\   12 -/   44 -\   18
               42  |   12  |   42  /-> 18  |   42
               94  |   42  \-> 55  |   42  \-> 44
               18  |   94 -\   18 -/   55      55
               06 -/   18  |   67      67      67
               67      67  \-> 94      94      94
  Проходы:     /|\      |      /|\      |      /|\
                |      \|/      |      \|/      |
 procedure ShakerSort;
     var j,k,l,r: index; x: item;
 begin l:=2; r:=n; k:=n;
     repeat
      for j:=r downto l do
       if a[j-1].key > a[j].key then
    begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
                 k:=j;
    end;
   l:=k+1;
   for j:=l to r do
       if a[j-1].key > a[j].key then
    begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
        k:=j;
    end;
   r:=k-1;
  until l>r;
 end;
 
 Анализ алгоритма простого пузырька:
   Число сравнений
     C = 1/2 (n^2 - n),
  Числа пересылок:
    Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).
 
 Анализ шейкер-сортировки (из книги Д.Кнута):
   Минимальное число сравнений Cmin = n-1
   Среднее число проходов пропорционально n - k1*корень(n),
   Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
 
 Hо, как видно, все предложенные усовершенствования не влияют на число
 обменов. К сожалению, обмен - операция, как правило, гораздо более
 медленная, чем сравнение ключей, поэтому реальный эффект улучшений
 гораздо меньше, чем можно было бы ожидать.
 
   Метод пузырька и описанные улучшения на практике крайне неэффективны,
 SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
 использовать, когда известно, что элементы уже почти упорядочены.
 Hо даже в этом случае обычно применяют все же InsertSort, которая
 менее чувствительна к степени упорядоченности.
 
 ====================================================================
 
 > 5. Сортировка простыми вставками.
 
 ====================================================================
 
                                  Алгоритм
 
              Все элементы условно разделяются на готовую
         последовательность 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
 
     Примечания.
 
 1. Если мы работаем с массивом, а не списком, то искать место вставки
 очередного ai в готовую последовательность можно бинарным поиском,
 ведь a1..a_i-1 уже отсортированы!
 При этом количество сравнений  снизится до O(nlogn),
 но сортировка станет вести себя крайне неестественно (уже
 отсортированный массив обрабатывается дольше всего), а,
 самое главное, количество пересылок по-прежнему останется O(n^2).
 
 2. При работе с массивами можно использовать и другое улучшение
 InsertSort'a - ShellSort (описана в другом вопросе).
 
         Пример на Си - 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;
     }
 }
 
 ====================================================================
 
 > 6. Описание и исходник ShellSort (сортировка Шелла)
 
 ====================================================================
 
 Этот алгоритм - модификация сортировки простыми вставками.
 
 Идея, например, в случае 16 чисел n1 ... n16 такова:
 
 Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов
 (n1, n9), (n2, n10), ... , (n8, n16).
 
 Потом сортируем каждую из четырех групп по 4 элемента (n1, n5, n9, n13),
  ..., (n4, n8, n12, n16). Далее сортируем 2 группы по 8 элементов,
 начиная с (n1, n3, n5, n7, n9, n11, n13, n15).
 А в конце сортируем вставками все 16 элементов.
 
 Очевидно, лишь последняя сортировка необходима,
 чтобы расположить все элементы по своим местам.
 Так зачем нужны остальные ?
 
 Hа самом деле они продвигают элементы максимально близко
 к соответствующим позициям, так что в последней стадии число
 перемещений будет весьма невелико. Они и так почти рассортированы.
 
 Были проведены многочисленные исследования по вопросу,
 какова должна быть последовательность расстояний между сортируемыми
 элементами в зависимости от прохода (инкремент).
 
 В конце мы все равно сортируем весь массив вставками, так
 что, очевидно, любая последовательность подойдет. Hабор
  ..., 8, 4, 2, 1 - неплохой выбор, особенно,
 когда N - степень двойки. Hо гораздо лучше будет взять
 
 ( 3k - 1 )/2, ..., 40, 13, 4, 1
 Ее можно вычислить рекуррентно:
 
 i_1 = 1, i_k+1 = 3i_k + 1, k = 1, 2, ...
 При этой последовательности количество операций даже
 в наихудшем случае - порядка N^3/2.
 
 Для случайной последовательности при N < 60000
 количество операций, приблизительно, N^1.25,
 однако уже при N > 50 QuickSort быстрее.
 
 Исходник на Си.
 void shell(unsigned long n, float a[])
 {
     unsigned long i, j, inc;
  float v;
  inc=1;                         // начальный инкремент
  do {
      inc *=3;
   inc++;
  } while (inc <= n);
  do {                           // Цикл частичных сортировок
      inc /=3;
   // Внутренний цикл простых вставок
      for (i=inc+1; i<=n; i++) {
       v=a[i];
    j=i;
    while ( a[j-inc] > v) {
        a[j] = a[j-inc];
     j -= inc;
     if ( j <= inc ) break;
    }
    a[j]=v;
   }
  } while ( inc > 1 );
 }
 
 ====================================================================
 
 > 7. Сортировка двоичным деревом, 'древесная сортировка'.
 
 ====================================================================
 
     Двоичным(бинарным) деревом назовем упорядоченную структуру данных,
 в которой каждому элементу - предшественнику или корню (под)дерева -
 поставлены в соответствие по крайней мере два других элемента (преемника).
     Причем для каждого предшественника выполнено следующее правило:
 левый преемник всегда меньше, а правый преемник всегда больше или равен
 предшественнику.
    Вместо 'предшественник' и 'преемник' также употребляют термины
 'родитель' и 'сын'. Все элементы дерева также называют 'узлами'.
 
   При добавлении в дерево нового элемента его последовательно сравнивают
 с нижестоящими узлами, таким образом вставляя на место.
   Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
 с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
 и так далее, пока есть сыновья, с которыми можно сравнить.
 
  Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:
    44      44         44          44          44
             \        /  \        /  \        /  \
             55      12  55      12  55      12  55
                                   \           \   \
                                    42        42   94
 
 (**) 44              44         (*) 44
     /  \            /  \           /  \
    12  55          12  55         12   55
      \   \        /  \   \       /  \   \
      42  94      06  42  94     06  42   94
      /               /              /    /
    18             18             18    67
 
  Дерево может быть и более-менее ровным, как на (*), может и иметь всего
 две основные ветви (**), а если входная последовательность уже отсортирована,
 то дерево выродится в линейный список.
 
 Если мы будем рекурсивно обходить дерево по правилу
 "левый сын - родитель - правый сын", то, записывая все
 встречающиеся элементы в массив, мы получим упорядоченное
 в порядке возрастания множество. Hа этом и основана идея сортировки деревом.
 
 Более подробно правило обхода можно сформулировать как
   обойти левое поддерево - вывести корень - обойти правое поддерево,
 где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается
 с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.
 
 /*********** сортировка с помощью двоичного дерева *************/
 #include <stdio.h>
 #include <stdlib.h>
 === Cut ===
                  ъщю До следующих встреч, All ющъ
 --- GoldEd 3.00.Alpha4+
  * Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор