21 сентября 2010 в 19:57

Ещё раз про сортировку

Прошлый топик, про оценку сложности алгоритмов был весьма положительно оценён хабрасообществом. Из этого я могу сделать вывод, что тема базовых алгоритмов весьма интересна. Сегодня я хочу представить вам часть, посвящённую алгоритмам сортировки. Про базовые алгоритмы писать для Хабра совсем несерьёзно, а вот про сортировки Шелла, пирамидальную и быструю рассказать всё-таки стоит. (Если кому-то интересно почитать про базовые методы, милости прошу сюда)

Эффективные методы сортировки


Сортировка вставками с уменьшающимся расстоянием (сортировка Шелла)

В 1959 году Шелл предложил способ ускорить сортировку простыми вставками. Сначала каждая группа элементов, отстоящих друг от друга на k1 элементов, сортируется отдельно. Это процесс называется k1-сортировкой. После первого прохода рассматриваются группы элементов, но уже отстоящих друг от друга на k2 (k2<k1) позиций, и эти группы тоже сортируются по отдельности. Этот процесс называется k2-сортировкой. Так проводится несколько итераций, и в конце шаг сортировки становится равным 1.
Встаёт резонный вопрос: не превысят ли возможную экономию затраты на выполнение нескольких проходов, в каждом из которых сортируются все элементы? Однако, каждая сортировка одной группы элементов либо имеет дело с относительно небольшим их числом, либо элементы уже частично отсортированы, так что нужно сделать сравнительно немного перестановок.
Очевидно, что метод приводит к отсортированному массиву, и нетрудно понять, что на каждом шаге нужно выполнить меньше работы благодаря предыдущим итерациям (т.к. каждая ki сортировка комбинирует две группы, отсортированные предыдущей ki-1 сортировкой). Очевидно также, что допустима любая последовательность расстояний, лишь бы последнее из них было равно единице. Не так очевидно, что метод работает лучше, если уменьшающиеся расстояния выбирать отличными от степени двойки.
Приведём алгоритм для произвольной последовательности расстояний. Всего будет T расстояний h1,h2,…,hT, удовлетворяющих условиям: hT=1, hi+1<hi.
  1. procedure ShellSort;
  2. const
  3. T=5;
  4. var
  5. i,j,k,m: longint;
  6. x: longint;
  7. h: array [1..5] of integer;
  8. begin
  9.   h[1]:=31; h[2]:=15; h[3]:=7; h[2]:=3; h[1]:=1;
  10.   for m:=1 to T do
  11.   begin
  12.     k:=h[m];
  13.     for i:=to N do
  14.     begin
  15.       x:=a[i];
  16.       j:=i-k;
  17.       while (j>=k) and (x<a[j]) do
  18.       begin
  19.         a[j+k]:=a[j];
  20.         j:=j-k;
  21.       end;
  22.       if (j>=k) or (x>=a[j]) then
  23.         a[j+k]:=x
  24.       else
  25.       begin
  26.         a[j+k]:=a[j];
  27.         a[j]:=x;
  28.       end;
  29.     end;
  30.   end;
  31. end;

Анализ этого алгоритма – сложная математическая задача, у которой до сих пор нет полного решения. В настоящий момент неизвестно, какая последовательность расстояний даёт наилучший результат, но известно, что расстояния не должны быть кратными друг другу. Это необходимо, чтобы очередной проход не объединял две последовательности, до того никак не пересекавшиеся. На самом деле желательно, чтобы последовательности пересекались как можно чаще. Это связано со следующей теоремой: если последовательность после ki сортировке подвергается ki+1 сортировке, то она при этом остаётся ki сортированной.
Кнут предлагает в качестве последовательно уменьшающихся расстояний использовать одну из следующих последовательностей (приведены в обратном порядке): 1,4,13,40,121,…, где hi-1=3*hi+1 или 1,3,7,15,31,…, где hi-1=2*hi+1. В последнем случае математическое исследование показывает, что при сортировке N элементов алгоритмом Шелла затраты пропорциональны N1.2. Хотя это гораздо лучше, чем N2, мы не будем углубляться в этот метод, так как есть ещё более быстрые алгоритмы.

Пирамидальная сортировка (турнирная сортировка)

Простая сортировка выбором основана на повторном выборе наименьшего ключа среди N элементов, затем среди оставшихся N-1 элементов и т.д. Очевидно, для того, чтобы найти наименьший ключ среди n элементов нужно N-1 сравнений, среди N-1 элементов нужно N-2 сравнений и т.д. Очевидно, что сумма первых N-1 натуральных чисел равна (N2-N)/2. Эту сортировку можно улучшить, только если после каждого просмотра сохранять больше информации, чем всего лишь об одном наименьшем элементе. Например, N/2 сравнений позволяют определить меньший ключ в каждой паре, ещё N/4 сравнений дадут меньший ключ в каждой паре из уже найденных меньших ключей и т.д. Рассмотрим массив 12,18,42,44,55,67,94,6. Сделав n-1 сравнений, мы можем построить дерево выбора, причём в корне будет наименьший ключ.

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


Теперь элементом в корне дерева будет очередной наименьший ключ. Теперь можно удалить его. После N таких шагов в дереве не останется ни одного узла с ключом, и процесс сортировки на этом завершится. Очевидно, что на каждом из N шагов требуется log(N) сравнений, поэтому вся процедура требует порядка N*log(N) элементарных операций (помимо тех N шагов, которые нужны для построения дерева). Это значительное улучшение не только по сравнению с простыми методами, требующими N2 шагов, но и с сортировкой Шелла, требующей N1.2 шагов. Естественно, сложность элементарных шагов в этом алгоритме выше: чтобы сохранить всю информацию с предыдущего шага необходимо использовать некоторое дерево. Теперь нам необходимо найти способ эффективно организовать эту информацию.
В первую очередь надо избавиться от необходимости хранить пустые значения, которые, в конце концов, заполнят всё дерево и приведут к большому числу лишних сравнений. Затем надо найти способ сделать так, чтобы дерево занимало в памяти N единиц, вместо 2*N-1, как это происходит на рисунках. Обе цели были достигнуты в алгоритме HeapSort, названном так его изобретателем Вильямсом. Этот алгоритм является радикальным улучшением обычной турнирной сортировки.
Пирамидой (heap) называется последовательность ключей hL,hL+1,…,hR (L≥0), такая, что hi<h2i+1 и hi<h2i+2, для i=L…R/2-1. Получается, что любое двоичное дерево можно представить массивом, так, как показано на рисунке (при этом вершина пирамиды будет её наименьшим элементом).

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


В нашем примере мы расширим пирамиду числом h0=44. Сначала ключ 44 меняется местами с 6, а затем с 12. В итоге получаем искомое дерево. Мы сформулируем алгоритм просеивания в терминах пары индексов i,j, соответствующих элементам, которые обмениваются на каждом шаге просеивания.
Метод, который мы рассмотрим, и был предложен Флойдом. Основа метода процедура sift (просеивание). Если у нас есть массив h1…hN, то его элементы с номерами от m=N div 2 до N уже образуют пирамиду (т.к. в этих элементах нет таких пар i,j, чтобы j=2*i+1 или j=2*i+2). Эти элементы будут образовывать нижний ряд пирамиды. Заметим, что в нижнем ряду никакое упорядочивание не требуется. Затем начинается процесс расширения пирамиды. Причём за один шаг в неё будет включаться только один элемент, и этот элемент будет ставиться на своё место с помощью процедуры просеивания, которую мы сейчас рассмотрим.
  1. procedure sift(L,R: integer);
  2. var
  3. i,j: integer;
  4. x: longint;
  5. begin
  6.   i:=L;
  7.   j:=2*i;
  8.   x:=a[i];
  9.   if (j<R) and (a[j]<a[j+1]) then
  10.     j:=j+1;
  11.   while (j<=R) and (x<a[j]) do
  12.   begin
  13.     a[i]:=a[j];
  14.     i:=j;
  15.     j:=2*j;
  16.     if (j<R) and (a[j]<a[j+1]) then
  17.       j:=j+1;
  18.   end;
  19.   a[i]:=x;
  20. end;
  21.  

Процесс получения пирамиды можно описать следующим образом:
  1. L:=(div 2)+1;
  2. R:=N;
  3. while L>1 do
  4. begin
  5.   L:=L-1;
  6.   sift(L,R);
  7. end;
  8.  

Пирамида, которую мы получим, характеризуется тем, что в её вершине будет храниться наибольший (а не наименьший) ключ. Кроме того, полученный массив будет упорядочен не полностью. Для того, чтобы добиться полной упорядоченности нужно выполнить ещё N просеиваний и после каждого из них снимать с вершины очередной элемент. Возникает вопрос, где хранить снимаемые с вершины элементы. Существует довольно красивое решение этой задачи: нам необходимо взять последний элемент пирамиды (будем называть его x), записать элемент с вершины пирамиды в позицию, освободившуюся из под x, а элемент x поставить в правильную позицию очередным просеиванием. Этот процесс можно описать следующим образом:
  1. while R>1 do
  2. begin
  3.   x:=a[1];
  4.   a[1]:=A[R];
  5.   A[R]:=x;
  6.   R:=R-1;
  7.   sift(L,R);
  8. end;

Таким образом, алгоритм пирамидальной сортировки можно представить следующим кодом:
  1. procedure HeapSort;
  2.   procedure sift(L,R: integer);
  3.   var
  4.   i,j: integer;
  5.   x: longint;
  6.   begin
  7.     i:=L;
  8.     j:=2*i;
  9.     x:=a[i];
  10.     if (j<R) and (a[j]<a[j+1]) then
  11.       j:=j+1;
  12.     while (j<=R) and (x<a[j]) do
  13.     begin
  14.       a[i]:=a[j];
  15.       i:=j;
  16.       j:=2*j;
  17.       if (j<R) and (a[j]<a[j+1]) then
  18.         j:=j+1;
  19.     end;
  20.     a[i]:=x;
  21.   end;
  22. var
  23. L,R: integer;
  24. x: longint;
  25. begin
  26.   L:=(div 2)+1;
  27.   R:=N;
  28.   while L>1 do
  29.   begin
  30.     L:=L-1;
  31.     sift(L,R);
  32.   end;
  33.   while R>1 do
  34.   begin
  35.     x:=a[1];
  36.     a[1]:=A[R];
  37.     A[R]:=x;
  38.     R:=R-1;
  39.     sift(L,R);
  40.   end;
  41. end;


В этом алгоритме большие элементы сначала просеиваются влево, и только потом занимают окончательные позиции в правой части отсортированного массива. Из-за этого может показаться, что эффективность пирамидальной сортировки не очень высока. Действительно, для сортировки небольшого числа элементов лучше воспользоваться другими алгоритмами, но для больших N эта сортировка очень эффективна.
В худшем случае фаза создания пирамиды требует N/2 шагов просеивания, причём на каждом шаге элементы просеиваются через log(N/2),log(N/2+1),…,log(N-1) позиций. Затем фаза сортировки требует n-1 просеиваний с не более чем log(N-1),log(N-2),…,1 пересылок. Кроме того потребуется n-1 пересылок для того, чтобы поставить элементы с вершины пирамиды на свои места. Получается, что даже в наихудшем случае пирамидальная сортировка требует N*log(N) пересылок. Это свойство является важнейшей отличительной особенностью данного алгоритма.
Наилучшей производительности можно ожидать, если элементы изначально стоят в обратном порядке. Тогда фаза создания пирамиды не потребует пересылок. Среднее число пересылок равно N/2*log(N), а отклонения от этого значения довольно малы.

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

Два предыдущих метода были основаны на принципах вставки и выбора. Пришло время рассмотреть третий, основанный на принципе обмена. Пузырьковая сортировка оказалась наихудшей среди всех трёх простых алгоритмов, однако усовершенствование обменной сортировки даёт лучший из известных методов сортировки массивов.
Построение быстрой сортировки исходит из того, что для достижения максимальной эффективности желательно выполнять обмены между максимально удалёнными позициями. Пусть у нас есть N элементов, расставленных в обратном порядке. Можно отсортировать их всего лишь за N/2 обменов, сначала обменяв крайний левый и крайний правый элементы, а потом постепенно продвигаясь внутрь массива с обеих сторон. Разумеется, этот метод сработает, только если элементы в массиве упорядочены в обратном порядке. Но тем не менее именно на этой идее построен рассматриваемый метод.
Попробуем реализовать такой алгоритм: случайно выберем любой элемент (назовём его x). Будем просматривать массив слева, пока не найдём элемент ai>x, а затем справа, пока не найдём элемент. aj<x Затем выполним обмен двух найденных элементов и будем продолжать такой процесс, пока оба просмотра не встретятся где-то в середине массива. В результате получим массив, разделённый на две части: левую, с ключами меньшими (или равными) x, и правую с ключами большими (или равными) x. Сформулируем процесс разделения в виде процедуры:
  1. procedure partition;
  2. var
  3. i,j: integer;
  4. w,x: integer;
  5. begin
  6.   i:=1;
  7.   j:=n;
  8.   // выбрать наугад значение x
  9.   REPEAT
  10.     while a[i]<x do
  11.       i:=i+1;
  12.     while x<a[j] do
  13.       j:=j-1;
  14.     if i<=then
  15.     begin
  16.       w:=a[i];
  17.       a[i]:=a[j];
  18.       a[j]:=w;
  19.       i:=i+1;
  20.       j:=j-1;
  21.     end;
  22.   UNTIL i>j;
  23. end;

Теперь вспомним, что наша цель не просто разделить массив, но и отсортировать его. На самом деле от разделения до сортировки всего один небольшой шаг: после разделения массива нужно применить тот же процесс к обеим получившимся частям, затем к частям частей и т.д., пока каждая часть не будет состоять из одного элемента.
  1. procedure sort(L,R: integer);
  2. var
  3. i,j: integer;
  4. w,x: longint;
  5. begin
  6.   i:=L;
  7.   j:=R;
  8.   x:=a[(L+R) div 2];
  9.   REPEAT
  10.     while a[i]<x do
  11.       i:=i+1;
  12.     while x<a[j] do
  13.       j:=j-1;
  14.     if i<=then
  15.     begin
  16.       w:=a[i];
  17.       a[i]:=a[j];
  18.       a[j]:=w;
  19.       i:=i+1;
  20.       j:=j-1;
  21.     end;
  22.   UNTIL i>j;
  23.   if L<j then
  24.     sort(L,j);
  25.   if i<R then
  26.     sort(i,R);
  27. end;
  28. procedure QuickSort;
  29. begin
  30.   sort(1,N);
  31. end;


Чтобы изучить эффективность быстрой сортировки, нужно сначала исследовать поведение процесса разделения. После выбора разделяющего значения x просматривается весь массив, поэтому выполнится точно N сравнений. Если нам везёт, и в качестве границы всегда выбирается медиана (средний элемент массива), то каждая итерация разбивает массив пополам, и число необходимых проходов равно log(N). Тогда полное число сравнений равно N*log(N), а полное число обменов равно N*log(N)/6.
Конечно, нельзя ожидать, что с выбором медианы всегда будет так везти. Строго говоря, вероятность этого 1/N. Но показано, что ожидаемая эффективность быстрой сортировки хуже оптимальной только на множитель 2*ln(2).
Даже у алгоритма быстрой сортировки есть недостатки. При малых N его производительность можно оценить как удовлетворительную, но его преимущество заключается в лёгкости подключения простого метода для обработки сегментов. Ещё остаётся проблема наихудшего случая. Предположим, что каждый раз в качестве разделяющего элемента выбирается наибольшее значение в разделяемом сегменте. Тогда каждый шаг будет разделять фрагмент из N элементов на две последовательности из 1 и N-1 элементов, соответственно. Очевидно, что в наихудшем случае поведение оценивается величиной N2. Чтобы избежать наихудшего случая, было предложено выбирать элемент x, как медиану из трёх значений разделяемого сегмента. Такое дополнение не ухудшает алгоритм в общем случае, но сильно улучшит его поведение в наихудшем случае.
Горьков Алексей @GORKOFF
карма
216,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (39)

  • +11
    Сомневаюсь, что на Хабре очень много человек всего этого не знают.

    <irony>Во мне не умер наивный оптимист, да?</irony>
  • +3
    h_T=1, h_(i+1)<h_i

    Ужасно смотрится. Используйте тег
    <sub> </sub>
    для нижнего индекса.
    hi+1 намного симпатичнее.
    • 0
      Спасибо, исправил.
  • +23
    Сомневаюсь, что статья о простейших алгоритмах сортировки кому-то здесь полезна. Особенно с примерами на Паскале и неформатированным кодом.
    • +2
      зря сомневаетесь. Мне полезна, например.
  • 0
    Как минимум надо было еще написать сортировку слияниями — N*logN гарантированно, алгоритм простой. Но просит дополнительную память.
  • 0
    Я недавно прочитал про сортировку вычёрпыванием (bucket sort) — интересная, работает за линейное средее время, но не всегда =)
    • 0
      Тоже базовый алгоритм.

      Кому интересны базовые алгоритмы идут читать книжку от Cormen & Co, помню тут даже ссылку давали на русский перевод.
      • 0
        Там и прочитал) Раньше из линейных знал только Radix и сортировку подсчетом, они как-то больше на слуху.
      • 0
        а можно подробнее, о какой книге речь?
  • +1
    QuickSort вроде как раз базовый по самое нехочу

    Я уже кажется писал, но писать то, что чуть ли не дословно, а чаще понятнее и нагляднее, можно прочитать даже в Википедии постить не следует. Вот если бы были примеры использования, плюсы минусы в различных ситуациях, интересные реализации и тд — тогда это было бы кому нибудь полезным
  • +2
    Где мои любимые поразрядные сортировки? :(
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      И на будущее, не бывает меньшей и большей половины.
      • +4
        Правда большая половина людей, этого не понимает. :)
        • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Если тебе интересны алгоритмы, то тебе самая дорога в википедию или лучше в библиотеку — информации получишь больше, причем в понятной и наглядной форме.
      • 0
        В русской википедии некоторые алгоритмы описаны не очень подробно. К примеру сортировка пирамидой: ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
        • 0
          Смотри английскую версию. Если надо — подтяни англиский, все равно придется рано или поздно :)
          • 0
            Так я ж не для себя пишу, а для тех, кто пока не очень хорош в английском.
            • 0
              А я не заметил что вы автор.

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

              Quicksort скажем проще всего пянять по картинке, а HeapSort по анимации процесса. Кроме того нужно сначала рассказть про такой тип данных как Heap, а сам алгоритм написать в псевдокоде и разбить на 3 части — Build-Max/MinHeap, Max/Min Heapify и HeapSort — все сразу будет понятнее и нагляднее.

              Схемы кстати можно не рисовать, их полно в сети

              quicksort

              Кроме самого алгоритма нужен и его анализ и возможно доказательство. Не помешает показать как его можно рандомизовать, в стандартной краткой форме представить все его основные характеристики и тд. Тогда это будет хороший топик для тех, кто не знает такого алгоритма.
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Зря не описаны такие сортировки, как Поразрядная сортировка, к примеру. Сортирует за линейное время.
  • 0
    негодую! Хватит уже постить то, что можно прочитать в википедии, кормене, еще где-нибудь. Это же фундаментальные алгоритмы! Каждый программист это обязан знать. Такими темпами скоро и до определений массивов дойдем.
    Рассказали бы лучше модификации быстрой сортировки, области применения каждой сортировки. а так это бесполезная информация.
    • –1
      Быть может, каждый программист и обязан это знать, но 28 человек добавили этот топик в избранное, а значит, кому-то это всё-таки нужно, интересно, полезно.
  • +6
    А вот как выглядит быстрая сортировка (или точнее — алгоритм, похожий на быструю сортировку) на функциональном языке F#:

    let rec quicksort = function
                            | [] -> []
                            | h::t -> quicksort ([ for x in t do if x<=h then yield x]) 
                                      @ [h] @ quicksort ([ for x in t do if x>h then yield x]);;
    
    • 0
      Функциональное программирование определённо добро.
      • +3
        Этот пример стал классикой из разряда, «видите какое функциональное программирование крутое». Если набрать «сортировка Хоара f#» (или haskell), везде будет подобный пример.
        Только этот алгоритм совсем не сортировка Хоара, которая использует обмены. Он кушает много памяти. Честная же реализация будет иметь много строк.
  • 0
    а есть свободные реализации сортировки с использованием smp-фичи процессора?
  • 0
    и всё-равно абсолютно большая чать программистов будет использовать qsort() или любой другой встроенный метод сортировки и будут по-моему правы — кто-нибудь пробовал тестировать скорость работы того же qsort и собственноручно написанной быстрой сортировки? я еще не встречал людей, которым удалось бы его обогнать =)
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Спасибо. Разумеется имеется в виду это:
      h[1]:=31; h[2]:=15; h[3]:=7; h[4]:=3; h[5]:=1;
    • 0
      А если говорить о смысле кода, то это сортировка с постоянно уменьшающимся шагом. Сначала с шагом 31, потом 15, потом 7 и т.д.
  • +1
    Изобилие выражений «очевидно» и «нетрудно понять» навевает на мысль о копипасте с учебника. Либо у тебя уже такой академический стиль )
    anyway, приятно видеть знакомое имя на хабре ;-)
  • 0
    юзайте сортировку хоара

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.