Бързо сортиране

Бързо сортиране (на английски: quick sort) е добре известен сортиращ алгоритъм, разработен от Ч. А. Р. Хор през 1960 г.^[1] и публикуван през 1961 г.,^[2]. Основната част на алгоритъма се състои в сравняващо сортиране.

В най-лошия случай алгоритъмът има сложност O(n²). Средната времева сложност е O(n log n), а амортизираната сложност е 1,386 n log n сравнения. В практиката бързото сортиране е с по-добро време от други сортиращи алгоритми с време O(n log n). Освен това, последователността на бързото сортиране и локализираните препратки към паметта работят добре с кеша. Бързото сортиране се основава на сравнения. То не е устойчиво, тоест може да размества елементи с еднакви ключове. Класическият алгоритъм използва допълнителен масив, но съществува вариант, който сортира данните на място – без заделяне на втори масив, така че се използва само O(log n) допълнителна памет.

История

Алгоритъмът за бързо сортиране е разработен през 1960 година от Тони Хор по време на престоя му като стипендиант в Московския държавен университет в СССР. По това време Хор работел по проект за машинен превод за Националната физична лаборатория. Той разработил алгоритъма, за да сортира думите за превод и да ги адаптира по-лесно към вече сортиран руско-английски речник, запазен на магнитна дискета.

Принцип на действие

Избира се „главен“ елемент от списъка с елементи, които ще бъдат сортирани.
Списъкът се пренарежда така, че всички елементи, които са по-малки от „главния“ се поставят вляво от него, а всички, които са по-големи – вдясно от него.
Рекурсивно се повтарят горните стъпки върху списъка с по-малките и списъка с по-големите елементи.
Получените списъци се сливат (конкатенация) и се получава сортираният списък.

Пример

[5 3 2 8 7 6 1 9 4]

За „главен“ елемент избираме 5. Разделяме списъка на три части: елементи, по-малки от „главния“, „главния“, елементи, по-големи от главния.

[3 2 1 4] | [5] | [8 7 6 9]

Рекурсивно извършваме действията върху новополучените списъци.

[2 1] | [3] | [4] | [5] | [7 6] | [8] | [9]

[1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9]

Свързваме отделните списъци и получаваме сортирания списък.

[1 2 3 4 5 6 7 8 9]

Опростен вариант

С помощта на опростен псевдокод, можем да видим реализацията на алгоритъма:

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // масив от нула или един елементи е вече сортиран
      select and remove a pivot element 'pivot' from 'array'  // вижте избор на "главен" елемент по-долу
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), list('pivot'), quicksort('greater')) // две рекурсивни извиквания

Пълен пример за бързо сортиране на случаен набор от числа. Потъмненият елемент е „главният“. Винаги бива избран като последен елемент от дяла. Въпреки това, избирането на крайния елемент като главен в случая води до лоши резултати ( $O(n^{2})$ ) за *вече сортираните* списъци.

Забележете, че елементите биват проверявани единствено чрез сравнение с другите елементи и затова бързото сортиране е сортиране чрез сравнение.

Коректността на алгоритъма се базира на следните два аргумента:

При всяка итерация, вече обработените елементи се намират на желаната позиция: преди „главния“ елемент, ако са по-малки от него и след „главния“ елемент, ако са по-големи от него.
Всяка итерация намалява с един броя на елементите, които все още не са подредени.

Верността на целия алгоритъм се доказва с индукция: за нула или един елемент алгоритъмът оставя данните непроменени; за по-голям набор от данни, алгоритъмът конкатенира две части – елементи, по-малки от „главния“ и елементи, по-големи от него.

In-place вариант

Недостатъкът на опростения вариант по-горе е в това, че той се нуждае от O(n) допълнителна памет, което е недостатък и на сортирането чрез сливане. Заделянето на допълнителна памет може значително да намали скоростта за изпълнение в практическото приложение. Съществува по-сложен вариант на алгоритъма, при който не се заделя допълнителна памет и пълното сортиране може да бъде постигнато, използвайки средно O(log n) памет (без въведените данни). Започваме с разделяща функция:

   // left е индекса на най-левия елемент от подмножеството
   // right е индекса на най-десния елемент от подмножеството
   // брой на елементите в подмножеството = right-left+1
   function partition(array, left, right, pivotIndex)
      pivotValue := array[pivotIndex]
      swap array[pivotIndex] and array[right]  // преместваме "главния" елемент в края
      storeIndex := left
      for i from left to right – 1  // left ≤ i < right
          if array[i] < pivotValue
              swap array[i] and array[storeIndex]
              storeIndex := storeIndex + 1
      swap array[storeIndex] and array[right]  // преместваме "главния" елемент на финалната му позиция
      return storeIndex

Това е алгоритъмът, който заделя памет на място. Той разделя масива на две части – left и right – поставяйки по-малките елементи вляво, а по-големите или равни – вдясно. В процеса на обработка на данните се намира място и за главния елемент. Тъй като алгоритъмът само размества елементите, в края на сортирането ние разполагаме със същите елементи. Трябва да се отбележи, че даден елемент може да смени позицията си няколко пъти, докато намери своето окончателно място. Също така, в случай че главният елемент е равен по стойност на някой друг, те ще бъдат разделени и поставени на различни позиции. Това не представлява грешка при разделянето, тъй като в крайна сметка тези елементи ще бъдат слепени заедно.

Този вариант на алгоритъма не е неговата оригинална форма; многобройни варианти могат да бъдат намерени в различни учебници. Въпреки това, този начин вероятно е един от най-лесните за разбиране.

След като вече го имаме, написването на бързото сортиране е лесно:

  function quicksort(array, left, right)

      // ако списъкът има два или повече елемента
      if left < right

          // Вижте секцията "Избор на главен елемент" по-долу за възможните варианти
          choose any pivotIndex such that left ≤ pivotIndex ≤ right

          // Намерете списъците с по-малките и по-големите елементи, както и позицията на избрания главен елемент
          pivotNewIndex := partition(array, left, right, pivotIndex)

          // Рекурсивно сортирайте елементите, по-малки от главния елемент
          quicksort(array, left, pivotNewIndex – 1)

          // Рекурсивно сортирайте елементите, по-малки или равни на главния елемент
          quicksort(array, pivotNewIndex + 1, right)

Всяко рекурсивно извикване на тази функция за бързо сортиране намалява размера на масива, който остава да бъде сортиран, поне с един елемент, тъй като при всяко извикване на елемент като „главен“, той се поставя на окончателната му позиция. По този начин се гарантира, че алгоритъмът ще приключи своето изпълнение след n извиквания. Все пак, тъй като елементите се пренареждат в рамките на всеки дял, този вариант на бързо сортиране е нестабилен.

Реализация

Избор на главен елемент

В най-ранните версии на бързото сортиране често най-левият елемент е бил избиран за главен. Това не работи при вече сортирани масиви, които са доста често срещан случай. Проблемът бил лесно решен, като се избирал или произволен индекс за главен елемент, или средният елемент на дяла, или (особено за по-дълги редици) медианата на първия, средния и последния елемент на дяла (както препоръчвал Робърт Седжуик).

Избирането на главния елемент е трудно също и при наличието на препълване на целочисления тип. Ако граничните показатели на подмножеството, което трябва да бъде сортирано, са достатъчно големи, изразът за намиране на средния индекс, (left + right)/2, ще доведе до препълване на целочисления тип и ще даде невалиден индекс за главен елемент. Това може да бъде избегнато, използвайки израза left + (right-left)/2 за намиране на индекса на средния елемент, с цената на по-сложна аритметика. Подобни проблеми възникват и в някои други методи за избиране на главен елемент.

Оптимизация

Съществуват още две важни оптимизации, за които обикновено се счита, че също са предложени от Р. Седжуик, и са широко използвани в практиката:

За да е сигурно, че се използва най-много O(log N) място, първо използваме рекурсия в по-малката част на масива, а за другата използваме опашкова рекурсия (tail call).
С оглед на алгоритъма за сортиране чрез вмъкване, който има по-малък константен фактор и по тази причина е по-ефективен при къси масиви, чиито дължини са по-малки от граничната стойност k, която се определя експериментално. На практика това може да се реализира чрез спиране на рекурсията, когато остават по-малко от k елемента, тоест всеки елемент ще бъда на най-много k позиции от крайното си местоположение. След това едно изпълнение на сортиране чрез вмъкване завършва подреждането за O(k×n) време. Отделното сортиране чрез вмъкване на всеки малък сегмент увеличава времето за обработка чрез стартиране и спиране на много малки сортирания, но спестява усилията за сортиране на ключовете в краищата на сегмента, тъй като ключовете ще са подредени заради начина, по който работи бързото сортиране.

Паралелна обработка

Сортирането чрез вмъкване, както и бързото сортиране, които са алгоритми от типа „разделяй и владей“, могат да бъдат изпълнявани паралелно. Отделните операции по разделянето се паралелизират трудно, но след като масивът е разделен, отделните секции могат да се сортират паралелно. Най-лесният подход при p процесора е да се раздели масив от n елемента на p подсписъка за средно време O(n) и да се сортира всеки от тях за средно време $\textstyle O\left({\frac {n}{p}}\log {\frac {n}{p}}\right)$ . Ако се игнорира времето за предварителна обработка и разделяне, което е O(n), се постига линейно ускорение. Ако се приложи сляпо разделяне без отчитане на стойностите, сливането отнема O(n). Разделянето на база главен елемент е сложно и в общия случай отнема O(n). При O(log n) или повече процесора ще бъде необходимо O(n) време, докато методът с линейно ускорение ще достигне време O(log n).

Едно от предимствата на това просто паралелно бързо сортиране пред останалите паралелни сортиращи алгоритми е, че не е необходима синхронизация, но сортирането отнема O(n) и се постига ускорение от O(log n). Обработката на нова нишка започва веднага след като има готов подсписък и не е необходима комуникация с останалите нишки. Сортирането приключва, когато всички нишки са готови.

По-сложни паралелни алгоритми могат да постигат по-добри резултати. Например през 1991 г. Дейвид Пауърс описва паралелно бързо сортиране (и свързаният Radix sort), което за O(log n) време на CRCW PRAM с n процесора извършва имплицитно разделяне.

Сравнение с други сортиращи алгоритми

Бързото сортиране е версия на бинарното дървовидно сортиране, оптимизирана по памет. При бързото сортиране елементите не се вмъкват последователно в определена дървовидна структура, а едновременно сформират дърво, което се получава при рекурсивното извикване. Алгоритмите извършват едни и същи сравнения, но в различна последователност. Желана характеристика на алгоритмите за сортиране е стабилността – запазване на позицията на равни елементи, което позволява контролиране на последователността на многоключови таблици (напр. директории или папки) по естествен начин. Тази характеристика е трудно да се поддържа при бързото сортиране на място, което използва константна допълнителна памет за указатели и буфериране и logN допълнително пространство за експлицитна или имплицитна рекурсия. При варианта на бързо сортиране, който използва допълнителна памет за структури с указатели (напр. списъци и дървета) или файлове (списъци) поддържането на стабилност е лесно. По-сложните дискови структури от данни увеличават времето и използването на виртуална памет или дисково пространство.

Най-близкият конкурент на бързото сортиране е пирамидалното сортиране. При него най-лошото време винаги е O(log n), но пирамидалното сортиране като цяло се счита за по-бавно от стандартното бързо сортиране. Съществуват публикации, които оборват това твърдение. Introsort е вариант на бързото сортиране, който използва пирамидално сортиране, когато се открие лош сценарий, като по-този начин се избягва най-лошото време на бързото сортиране. Ако предварително е известно, че ще е необходимо използване на пирамидалното сортиране, е по-бързо то да се приложи директно, вместо да се чака introsort да го извика.

Сортиране чрез сливане е друг рекурсивен алгоритъм, който е сравним с бързото сортиране, като най-лошото му време е O(log n). Той е стабилен алгоритъм за разлика от бързото сортиране на място и пирамидалното сортиране и лесно може да се адаптира за използване в свързани списъци и много големи списъци, съхранявани на бавни носители като дискове или мрежови хранилища. Бързото сортиране също може да бъде имплементирано като стабилно сортиране на място, но това се прави рядко. Ако бързото сортиране се използва при свързани списъци често ще се наблюдава лош избор на главен елемент без случайност. Основният недостатък на сортирането чрез сливане е необходимостта от O(n) допълнително пространство за обработка на масиви, докато основният вариант на бързото сортиране на място и опашковата рекурсия използват само O(log n). (Трябва да се отбележи, че когато сортирането чрез сливане се използва при свързани списъци той използва константна, малка по обем, спомагателна памет за съхранение).

Блоковото сортиране с два блока е много сходно с бързото сортиране – главният елемент е средния елемент от поредицата, което е добре при равномерно разпределени входни данни.

Източници

↑ Hoare/ Sir Antony Hoare // Computer History Museum. Посетен на 22 април 2015.^{[неработеща препратка]}
↑ Hoare, C. A. R. Algorithm 64: Quicksort // Comm. ACM 4 (7). 1961. DOI:10.1145/366622.366644. с. 321.

Външни препратки

Уикикниги

В Уикикниги има на разположение:

Quicksort

Interactive Tutorial for Quicksort
Quicksort applet with „level-order“ recursive calls to help improve algorithm analysis
Open Data Structures – Section 11.1.2 – Quicksort
Multidimensional quicksort in Java Архив на оригинала от 2005-11-24 в Wayback Machine.
Literate implementations of Quicksort in various languages Архив на оригинала от 2008-05-09 в Wayback Machine. on LiteratePrograms
A colored graphical Java applet Архив на оригинала от 2012-02-18 в Wayback Machine. which allows experimentation with initial state and shows statistics

Тази страница частично или изцяло представлява превод на страницата Quicksort в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] Hoare/ Sir Antony Hoare // Computer History Museum. Посетен на 22 април 2015.^{[неработеща препратка]}

[alg64-2] Hoare, C. A. R. Algorithm 64: Quicksort // Comm. ACM 4 (7). 1961. DOI:10.1145/366622.366644. с. 321.

[1]

[2]