Устойчивая сортировка

Устойчивая сортировка

Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи.

Устойчивость является очень важной характеристикой алгоритма сортировки, но, тем не менее, она практически всегда может быть достигнута путём удлинения исходных ключей за счёт дополнительной информации об их первоначальном порядке. Несмотря на кажущуюся необходимость, вытекающую из названия, устойчивость совсем не обязательна для правильности сортировки и чаще всего не соблюдается, так как для её обеспечения практически всегда необходимы дополнительная память и время.

Содержание

Пример

При сортировке записей вида (фамилия, имя, отчество) по фамилии значения ключей для Иванов Сергей и Иванов Иван будут одинаковы, поэтому устойчивая сортировка не переставит Сергея и Ивана местами (Python 3, сортировка timsort[1]):

records = [
   {'фамилия': 'Иванов',  'имя': 'Сергей', 'отчество': 'Михайлович',},
   {'фамилия': 'Иванов',  'имя': 'Иван',   'отчество': 'Борисович',},
   {'фамилия': 'Абрамов', 'имя': 'Юрий',   'отчество': 'Петрович',},
]
records.sort(key=lambda x: x['фамилия'])  # сортировка по ключу "фамилия"
for r in records:
    print('%-12s %-12s %-12s' % (r['фамилия'], r['имя'], r['отчество']))

В результате записи будут отсортированы только по фамилии, с сохранением исходного порядка среди записей с одинаковыми фамилиями:

Абрамов      Юрий         Петрович    
Иванов       Сергей       Михайлович  
Иванов       Иван         Борисович

Алгоритмы устойчивой сортировки

Ниже приводятся описания алгоритмов устойчивой сортировки с временем работы не хуже O(n log2 n) (кроме наихудших случаев в алгоритме с использованием устойчивого разделения). Во всех псевдокодах пара косых // означает комментарий до конца строки как в языке C++.

Сортировка слиянием с дополнительной памятью

При этом алгоритме сортировки сначала осуществляется рекурсивное разделение исходного массива на части до тех пор, пока в каждой части массива не окажется один или ноль элементов (на каждом шаге рекурсии осуществляется разделение пополам). После этого полученные части попарно «сливаются». Общая сложность алгоритма — O(n log n), при этом алгоритму требуется O(n) дополнительной памяти для хранения слитых массивов.

Сортировка с использованием устойчивого разделения

Данный алгоритм похож на алгоритм быстрой сортировки. Так же как и в алгоритме быстрой сортировки, в данном алгоритме исходный массив разделяется на две части — в одной все элементы меньше или равны некоторому опорному элементу, а в другой — больше или равны. После этого разделённые части массива рекурсивно сортируются таким же образом. Отличие этого алгоритма от алгоритма быстрой сортировки в том, что здесь используется устойчивое разделение вместо неустойчивого. Ниже приведена реализация данного алгоритма на псевдокоде:

Sort(a[1..n])
if(n > 1) then
  N ← a[ 1 ];
  m ← StablePartition(a[1..n], N);
  Sort(a[1..m]);
  Sort(a[m+1..n]);
StablePartition(a[1..n], N)
if( n > 1 ) then
  m ←  \lfloor  n/2  \rfloor ;
  m1 ← StablePartition(a[1..m], N);
  m2 ← m+StablePartition(a[m+1..n], N);
  Rotate(a[m1..m2], m);
  return(m1 + (m2-m));
else
  if(a[1] < N) then
    return(1);
  else
    return(0)

Процедура Rotate:

Rotate(a[1..n], m)
if( n > m > 1 )        //в массиве хотя бы два элемента и сдвиг имеет смысл
  shift ← m-n;           //число позиций на которое будет осуществляться  сдвиг
  gcd ← GCD(m-1, n);   //GCD - это наибольший общий делитель
  for i ← 0 to gcd-1 do
    head ← i+1;
    headVal ← a[head];
    current ← head;
    next ← head+shift;
    while(next\nehead) do
      a[current] ← a[next];
      current ← next;
      next ← next+shift;
      if(next>n)
        next ← next-n;
    a[current] ← headVal;

Для устойчивого разделения массива требуется O(n log n) элементарных операций. Так как «глубина» осуществляемого рекурсивного спуска в среднем случае составляет O(log n) то общая сложность алгоритма составляет O(n log² n). При этом алгоритму для осуществления рекурсии потребуется O(log n) стековой памяти, хотя в худшем случае общая сложность равна O(n² log n) и требуется O(n) памяти.

Алгоритмы сортировки слиянием без дополнительной памяти

Все описанные ниже алгоритмы основаны на слиянии уже отсортированных массивов без использования дополнительной памяти сверх O(log² n) стековой памяти (это — т. н. условие минимальной памяти[2]) и отличаются лишь алгоритмом слияния. Далее приведен псевдокод алгоритмов (алгоритмы слияния — процедура Merge — приводятся отдельно для каждого метода):

Sort(a[1..n])
if( n > 1 ) then
  m← n/2 ;
  Sort(a[1..m]);
  Sort(a[m+1..n]);
  Merge(a[1..n], m);

Алгоритм Пратта

В алгоритме Пратта в отсортированных массивах находят два элемента α и β, которые являются медианами массива, состоящего из элементов обоих массивов. Тогда весь массив можно представить в виде aαbxβy. После этого осуществляется циклический сдвиг элементов в результате чего получаем такую последовательность: axβαby. Далее алгоритм слияния рекурсивно повторятся для массивов ax и by.

Merge(a[1..n], m)
if(m <> 1 and m <> n)   //это условие означает, что в массиве должно быть хотя бы 2 элемента
  if( n-1 > 2 )                                      //случай, когда элементов ровно два, приходится рассматривать отдельно
    if( m-1 > n-m )
      leftBound←1;
      rightBound←m;
      while( leftBound < rightBound ) do               //в этом цикле ищем медианы
       m1 ←  (leftBound+rightBound)/2;
       m2 ← FindFirstPosition(a[m..n], a[ m1 ]);        //реализация процедуры FindFirstPosition см. след. пункт
       if( m1 + (m2-m) > n/2 ) then
          rightBound ← m1-1;
       else
          leftBound ← m1+1;
    Rotate(a[m1..m2], m);
    Merge(a[1..m1+(m2-m)], m1);
    Merge(a[m1+(m2-m)+1..n], m2);
  else
    if(a[m] < a[1])
      a[m]\longleftrightarrowa[1];

Циклический сдвиг элементов требует O(n) элементарных операций и O(1) дополнительной памяти, а поиск медиан в двух уже отсортированных массивах — O(log² n) элементарных операций и O(1) дополнительной памяти. Так как осуществляется O(log n) шагов рекурсии, то сложность такого алгоритма слияния составляет O(n log n), а общая сложность алгоритма сортировки — O(n log² n). При этом алгоритму потребуется O(log² n) стековой памяти.

Алгоритм без поиска медиан

От поиска медиан в предыдущем алгоритме можно избавиться следующим образом. В большем из двух массивов выбираем средний элемент α (опорный элемент). Далее в меньшем массиве находим позицию первого вхождения элемента большего или равного α. Назовем его β. После этого осуществляется циклический сдвиг элементов так же как и в алгоритме Пратта (aαbxβyaxβαby) и осуществляется рекурсивное слияние полученных частей. Псевдокод алгоритма слияния приведен ниже.

Merge(a[1..n], m)

if(m <> 1 and m <> n)   //это условие означает что в массиве должно быть хотя бы 2 элемента
  if( n-1 > 2 )             //случай когда элементов ровно два приходится рассматривать отдельно
    if( m-1 > n-m )
      m1 <  (m+1)/2 ;
      m2 < FindFirstPosition(a[m..n], a[ m1 ]);
    else
      m2 < (n+m)/2 ;
      m1 < FindLastPosition(a[1..m], a[ m2 ]);
    Rotate(a[m1..m2], m);
    Merge(a[1..m1+(m2-m)], m1);
    Merge(a[m1+(m2-m)+1..n], m2);
  else
    if(a[ m ] < a[ 1 ])
      a[ m ]\longleftrightarrowa[ 1 ];

Процедуры FindFirstPosition и FindLastPosition практически совпадают с процедурой двоичного поиска:

FindFirstPosition(a[1..n], x)
leftBound < 1;
rightBound < n;
current < 1;
while(leftBound < rightBound) do
  current < [(leftBound+rightBound)/2];
  if(a[ current ] < x) then
    leftBound < current+1
  else
    rightBound < current;
return(current);

FindLastPosition(a[1..n], x)

leftBound < 1;

rightBound < n;

current < 1;

while(leftBound < rightBound) do
  current < [(leftBound+rightBound)/2];
  if( x < a[ current ] ) then
    rightBound < current;
  else
    leftBound < current+1
return(current);

В отличие от алгоритма Пратта в данном алгоритме разбиение может быть существенно неравным. Но даже в худшем случае алгоритм разобьёт весь диапазон [a..y] в соотношении 3:1 (если все элементы второго диапазона будут больше или меньше опорного и при этом оба диапазона имеют равное число элементов). Это гарантирует логарифмическое число шагов рекурсии при слиянии любых массивов. Таким образом получаем, что так же, как и в алгоритме Пратта, сложность алгоритма слияния равна O(n log n), сложность алгоритма сортировки — O(n log² n), а требуемая память — O(log² n).

Устойчивая сортировка без дополнительной памяти за время O(n log n)

Пути улучшения алгоритмов

  • Во всех вышеприведённых алгоритмах при разбиении исходного массива на части рекурсивное разбиение можно остановить, если размер разбиваемого массива станет достаточно маленьким. Тогда можно применить какой-либо из простых алгоритмов сортировки (например, сортировка вставками), которые, как известно, работают быстрее чем сложные, если размер входного массива невелик. Фактически данный прием применим не только для представленных здесь алгоритмов, но и для любого другого алгоритма, где применяется рекурсивное разбиение исходного массива (например, обычная нестабильная быстрая сортировка). Конкретное число входных элементов, при котором надо переходить на простой алгоритм сортировки, зависит от используемой вычислительной машины.
  • В алгоритме Пратта, алгоритме без поиска медиан и алгоритме с использованием устойчивого разделения вместо того, чтобы каждый раз рекурсивно вызывать процедуру слияния, можно динамически выделить массив временных переменных. Тогда можно будет продолжать разбиение диапазона лишь до тех пор, пока число элементов в большем диапазоне не станет меньше или равно вместимости временного массива. Фактически на некотором шаге рекурсии алгоритм Пратта и алгоритм без поиска медиан превращаются в алгоритм простого слияния. Т. о. если в системе достаточно динамической памяти, то асимптотическое время работы можно довести до O(n log n) вместо O(n log² n).

Примечания

  1. Tim Sort, c2.com
  2. Кнут Д., Искусство программирования. т. 3, Сортировка и поиск, М., Вильямс, 2000



Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Устойчивая сортировка" в других словарях:

  • Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort)  простой алгоритм сортировки. Для понимания и реализации этот алгоритм  простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… …   Википедия

  • Сортировка Шелла — (англ. Shell sort)  алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными… …   Википедия

  • Сортировка выбором — (Selection sort)  алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… …   Википедия

  • Сортировка вставками — Сортировка вставками  простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до …   Википедия

  • Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в)… …   Википедия

  • Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… …   Википедия

  • Сортировка расчёской — (англ. comb sort)  это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine …   Википедия

  • Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п …   Википедия

  • Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. …   Википедия

  • Пирамидальная сортировка — Анимированная схема алгоритма Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1])  …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»