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

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

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

Пример

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

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

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

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

Применение

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

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

Ниже приводятся описания алгоритмов устойчивой сортировки с временем работы не хуже O(n log² 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 ← ⌊ n/2 ⌋;
   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 ≠ head) 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) стековой памяти (это — т. н. условие минимальной памяти) и отличаются лишь алгоритмом слияния. Далее приведён псевдокод алгоритмов (алгоритмы слияния — процедура 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]⟷a[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βy → axβα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 ]⟷a[ 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).

Отрывок, характеризующий Устойчивая сортировка

– Нет, это хор из Водоноса, слышишь! – И Наташа допела мотив хора, чтобы дать его понять Соне.
– Ты куда ходила? – спросила Наташа.
– Воду в рюмке переменить. Я сейчас дорисую узор.
– Ты всегда занята, а я вот не умею, – сказала Наташа. – А Николай где?
– Спит, кажется.
– Соня, ты поди разбуди его, – сказала Наташа. – Скажи, что я его зову петь. – Она посидела, подумала о том, что это значит, что всё это было, и, не разрешив этого вопроса и нисколько не сожалея о том, опять в воображении своем перенеслась к тому времени, когда она была с ним вместе, и он влюбленными глазами смотрел на нее.
«Ах, поскорее бы он приехал. Я так боюсь, что этого не будет! А главное: я стареюсь, вот что! Уже не будет того, что теперь есть во мне. А может быть, он нынче приедет, сейчас приедет. Может быть приехал и сидит там в гостиной. Может быть, он вчера еще приехал и я забыла». Она встала, положила гитару и пошла в гостиную. Все домашние, учителя, гувернантки и гости сидели уж за чайным столом. Люди стояли вокруг стола, – а князя Андрея не было, и была всё прежняя жизнь.
– А, вот она, – сказал Илья Андреич, увидав вошедшую Наташу. – Ну, садись ко мне. – Но Наташа остановилась подле матери, оглядываясь кругом, как будто она искала чего то.
– Мама! – проговорила она. – Дайте мне его , дайте, мама, скорее, скорее, – и опять она с трудом удержала рыдания.
Она присела к столу и послушала разговоры старших и Николая, который тоже пришел к столу. «Боже мой, Боже мой, те же лица, те же разговоры, так же папа держит чашку и дует точно так же!» думала Наташа, с ужасом чувствуя отвращение, подымавшееся в ней против всех домашних за то, что они были всё те же.
После чая Николай, Соня и Наташа пошли в диванную, в свой любимый угол, в котором всегда начинались их самые задушевные разговоры.


– Бывает с тобой, – сказала Наташа брату, когда они уселись в диванной, – бывает с тобой, что тебе кажется, что ничего не будет – ничего; что всё, что хорошее, то было? И не то что скучно, а грустно?
– Еще как! – сказал он. – У меня бывало, что всё хорошо, все веселы, а мне придет в голову, что всё это уж надоело и что умирать всем надо. Я раз в полку не пошел на гулянье, а там играла музыка… и так мне вдруг скучно стало…
– Ах, я это знаю. Знаю, знаю, – подхватила Наташа. – Я еще маленькая была, так со мной это бывало. Помнишь, раз меня за сливы наказали и вы все танцовали, а я сидела в классной и рыдала, никогда не забуду: мне и грустно было и жалко было всех, и себя, и всех всех жалко. И, главное, я не виновата была, – сказала Наташа, – ты помнишь?
– Помню, – сказал Николай. – Я помню, что я к тебе пришел потом и мне хотелось тебя утешить и, знаешь, совестно было. Ужасно мы смешные были. У меня тогда была игрушка болванчик и я его тебе отдать хотел. Ты помнишь?
– А помнишь ты, – сказала Наташа с задумчивой улыбкой, как давно, давно, мы еще совсем маленькие были, дяденька нас позвал в кабинет, еще в старом доме, а темно было – мы это пришли и вдруг там стоит…
– Арап, – докончил Николай с радостной улыбкой, – как же не помнить? Я и теперь не знаю, что это был арап, или мы во сне видели, или нам рассказывали.
– Он серый был, помнишь, и белые зубы – стоит и смотрит на нас…
– Вы помните, Соня? – спросил Николай…
– Да, да я тоже помню что то, – робко отвечала Соня…
– Я ведь спрашивала про этого арапа у папа и у мама, – сказала Наташа. – Они говорят, что никакого арапа не было. А ведь вот ты помнишь!
– Как же, как теперь помню его зубы.
– Как это странно, точно во сне было. Я это люблю.
– А помнишь, как мы катали яйца в зале и вдруг две старухи, и стали по ковру вертеться. Это было, или нет? Помнишь, как хорошо было?
– Да. А помнишь, как папенька в синей шубе на крыльце выстрелил из ружья. – Они перебирали улыбаясь с наслаждением воспоминания, не грустного старческого, а поэтического юношеского воспоминания, те впечатления из самого дальнего прошедшего, где сновидение сливается с действительностью, и тихо смеялись, радуясь чему то.
Соня, как и всегда, отстала от них, хотя воспоминания их были общие.
Соня не помнила многого из того, что они вспоминали, а и то, что она помнила, не возбуждало в ней того поэтического чувства, которое они испытывали. Она только наслаждалась их радостью, стараясь подделаться под нее.
Она приняла участие только в том, когда они вспоминали первый приезд Сони. Соня рассказала, как она боялась Николая, потому что у него на курточке были снурки, и ей няня сказала, что и ее в снурки зашьют.
– А я помню: мне сказали, что ты под капустою родилась, – сказала Наташа, – и помню, что я тогда не смела не поверить, но знала, что это не правда, и так мне неловко было.
Во время этого разговора из задней двери диванной высунулась голова горничной. – Барышня, петуха принесли, – шопотом сказала девушка.
– Не надо, Поля, вели отнести, – сказала Наташа.
В середине разговоров, шедших в диванной, Диммлер вошел в комнату и подошел к арфе, стоявшей в углу. Он снял сукно, и арфа издала фальшивый звук.
– Эдуард Карлыч, сыграйте пожалуста мой любимый Nocturiene мосье Фильда, – сказал голос старой графини из гостиной.
Диммлер взял аккорд и, обратясь к Наташе, Николаю и Соне, сказал: – Молодежь, как смирно сидит!
– Да мы философствуем, – сказала Наташа, на минуту оглянувшись, и продолжала разговор. Разговор шел теперь о сновидениях.
Диммлер начал играть. Наташа неслышно, на цыпочках, подошла к столу, взяла свечу, вынесла ее и, вернувшись, тихо села на свое место. В комнате, особенно на диване, на котором они сидели, было темно, но в большие окна падал на пол серебряный свет полного месяца.
– Знаешь, я думаю, – сказала Наташа шопотом, придвигаясь к Николаю и Соне, когда уже Диммлер кончил и всё сидел, слабо перебирая струны, видимо в нерешительности оставить, или начать что нибудь новое, – что когда так вспоминаешь, вспоминаешь, всё вспоминаешь, до того довоспоминаешься, что помнишь то, что было еще прежде, чем я была на свете…
– Это метампсикова, – сказала Соня, которая всегда хорошо училась и все помнила. – Египтяне верили, что наши души были в животных и опять пойдут в животных.
– Нет, знаешь, я не верю этому, чтобы мы были в животных, – сказала Наташа тем же шопотом, хотя музыка и кончилась, – а я знаю наверное, что мы были ангелами там где то и здесь были, и от этого всё помним…
– Можно мне присоединиться к вам? – сказал тихо подошедший Диммлер и подсел к ним.
– Ежели бы мы были ангелами, так за что же мы попали ниже? – сказал Николай. – Нет, это не может быть!
– Не ниже, кто тебе сказал, что ниже?… Почему я знаю, чем я была прежде, – с убеждением возразила Наташа. – Ведь душа бессмертна… стало быть, ежели я буду жить всегда, так я и прежде жила, целую вечность жила.
– Да, но трудно нам представить вечность, – сказал Диммлер, который подошел к молодым людям с кроткой презрительной улыбкой, но теперь говорил так же тихо и серьезно, как и они.
– Отчего же трудно представить вечность? – сказала Наташа. – Нынче будет, завтра будет, всегда будет и вчера было и третьего дня было…
– Наташа! теперь твой черед. Спой мне что нибудь, – послышался голос графини. – Что вы уселись, точно заговорщики.
– Мама! мне так не хочется, – сказала Наташа, но вместе с тем встала.
Всем им, даже и немолодому Диммлеру, не хотелось прерывать разговор и уходить из уголка диванного, но Наташа встала, и Николай сел за клавикорды. Как всегда, став на средину залы и выбрав выгоднейшее место для резонанса, Наташа начала петь любимую пьесу своей матери.
Она сказала, что ей не хотелось петь, но она давно прежде, и долго после не пела так, как она пела в этот вечер. Граф Илья Андреич из кабинета, где он беседовал с Митинькой, слышал ее пенье, и как ученик, торопящийся итти играть, доканчивая урок, путался в словах, отдавая приказания управляющему и наконец замолчал, и Митинька, тоже слушая, молча с улыбкой, стоял перед графом. Николай не спускал глаз с сестры, и вместе с нею переводил дыхание. Соня, слушая, думала о том, какая громадная разница была между ей и ее другом и как невозможно было ей хоть на сколько нибудь быть столь обворожительной, как ее кузина. Старая графиня сидела с счастливо грустной улыбкой и слезами на глазах, изредка покачивая головой. Она думала и о Наташе, и о своей молодости, и о том, как что то неестественное и страшное есть в этом предстоящем браке Наташи с князем Андреем.
Диммлер, подсев к графине и закрыв глаза, слушал.
– Нет, графиня, – сказал он наконец, – это талант европейский, ей учиться нечего, этой мягкости, нежности, силы…
– Ах! как я боюсь за нее, как я боюсь, – сказала графиня, не помня, с кем она говорит. Ее материнское чутье говорило ей, что чего то слишком много в Наташе, и что от этого она не будет счастлива. Наташа не кончила еще петь, как в комнату вбежал восторженный четырнадцатилетний Петя с известием, что пришли ряженые.