From Wikipedia, the free encyclopedia
Бързо сортиране (на английски: quick sort) е добре известен сортиращ алгоритъм, разработен от Ч. А. Р. Хор през 1960 г.[1] и публикуван през 1961 г.,[2]. Основната част на алгоритъма се състои в сравняващо сортиране.
В най-лошия случай алгоритъмът има сложност O(n2). Средната времева сложност е 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) допълнителна памет, което е недостатък и на сортирането чрез сливане. Заделянето на допълнителна памет може значително да намали скоростта за изпълнение в практическото приложение. Съществува по-сложен вариант на алгоритъма, при който не се заделя допълнителна памет и пълното сортиране може да бъде постигнато, използвайки средно 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 за намиране на индекса на средния елемент, с цената на по-сложна аритметика. Подобни проблеми възникват и в някои други методи за избиране на главен елемент.
Съществуват още две важни оптимизации, за които обикновено се счита, че също са предложени от Р. Седжуик, и са широко използвани в практиката:
Сортирането чрез вмъкване, както и бързото сортиране, които са алгоритми от типа „разделяй и владей“, могат да бъдат изпълнявани паралелно. Отделните операции по разделянето се паралелизират трудно, но след като масивът е разделен, отделните секции могат да се сортират паралелно. Най-лесният подход при p процесора е да се раздели масив от n елемента на p подсписъка за средно време O(n) и да се сортира всеки от тях за средно време . Ако се игнорира времето за предварителна обработка и разделяне, което е 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). (Трябва да се отбележи, че когато сортирането чрез сливане се използва при свързани списъци той използва константна, малка по обем, спомагателна памет за съхранение).
Блоковото сортиране с два блока е много сходно с бързото сортиране – главният елемент е средния елемент от поредицата, което е добре при равномерно разпределени входни данни.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
