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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Нагледно бързо сортиране на списък с числа. Главният елемент е в червено.

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

В най-лошия случай алгоритъмът има сложност O(n2). В средния случай алгоритъмът има сложност O(log n), а в амортизирания се правят 1.386nlogn сравнения. В практиката бързото сортиране е по-бързо от други сортиращи алгоритми със сложност O(log n). Освен това последователността на бързото сортиране и локализираните препратки към паметта работят добре с кеша. Бързото сортиране е сортиране чрез сравняване и като такова не е особено стабилно за ефективни приложения. Бързото сортиране може да бъде имплементирано с алгоритъм без заделяне на допълнителна памет (in-place), така че цялото сортиране да бъде реализирано само с O(log n) допълнително място по време на рекурсията.

История[редактиране | edit source]

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

Принцип на действие[редактиране | edit source]

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

Пример[редактиране | edit source]

[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]

Опростен вариант[редактиране | edit source]

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

  1.   function quicksort('array')
  2.       if length('array')1
  3.           return 'array'  // масив от нула или един елементи е вече сортиран
  4.       select and remove a pivot element 'pivot' from 'array'  // вижте избор на "главен" елемент по-долу
  5.       create empty lists 'less' and 'greater'
  6.       for each 'x' in 'array'
  7.           if 'x''pivot' then append 'x' to 'less'
  8.           else append 'x' to 'greater'
  9.       return concatenate(quicksort('less'), list('pivot'), quicksort('greater')) // две рекурсивни извиквания
Пълен пример за бързо сортиране на случаен набор от числа. Потъмненият елемент е "главният". Винаги бива избран като последен елемент от дяла. Въпреки това, избирането на крайния елемент като главен в случая води до лоши резултати (O(n^2)) за вече сортираните списъци.

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

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

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

Пример за бързо сортиране.
In-place разделяне на малък списък. Маркираният елемент е главният, сините елементи са по-малки или равни, а червените са по-големи.

In-place вариант[редактиране | edit source]

Недостатъкът на опростения вариант по-горе е в това, че той се нуждае от 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 извиквания. Все пак, тъй като елементите се пренареждат в рамките на всеки дял, този вариант на бързо сортиране е нестабилен.

Имплементация[редактиране | edit source]

Избор на главен елемент[редактиране | edit source]

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

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

Оптимизация[редактиране | edit source]

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

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

Паралелна обработка[редактиране | edit source]

Сортирането чрез вмъкване, както и бързото сортиране, които са алгоритми от типа „разделяй и владей” могат да бъдат изпълнявани паралелно. Отделните операции по разделянето се паралелизират трудно, но след като масивът е разделен, отделните секции могат да се сортират паралелно. Най-лесният подход при 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 процесора извършва имплицитно разделяне.

Сравнение с други сортиращи алгоритми[редактиране | edit source]

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

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

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

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

Външни линкове[редактиране | edit source]

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