Преглед на бързо сортиране

Подобно на сортиране чрез сливане, бързото сортиране използва "разделяй и владей" и затова е рекурсивен алгоритъм. Бързото сортиране използва "разделяй и владей" по по-различен начин от сортирането чрез сливане. В сортирането чрез сливане стъпката за разделяне не прави почти нищо, а цялата реална работа се извършва в стъпката комбиниране. При бързото сортиране е обратното – реалната работа се извършва в стъпката "разделяй". Всъщност стъпката "комбинирай" в бързото сортиране не прави абсолютно нищо.

Има още няколко разлики между бързо сортиране и сортиране чрез сливане. Бързото сортиране работи на място. А най-лошото му време за изпълнение е като това на сортирането с пряка селекция и с вмъкване:

Θ (n^{2})

. Но средното време за изпълнение е като при сортиране чрез сливане:

Θ (n \log_{2} n)

. Защо тогава да мислим за бързо сортиране, щом сортирането чрез сливане е поне толкова добро? Това е така, защото константата, скрита в нотацията Θ за бързото сортиране, е доста добра. В практиката бързото сортиране превъзхожда сортирането чрез сливане и значително превъзхожда пряката селекция и сливането.

Ето как бързото сортиране използва "разделяй и владей". Както при сортирането чрез сливане, помисли за сортиране на подмасива array[p..r], където началният подмасив е array[0..n-1].

Разделяме, като изберем кой да е елемент от подмасива array[p..r]. Наричаме този елемент ос. Пренареждаме елементите в array[p..r] така, че всички елементи в array[p..r], които са по-малки или равни на оста, са от лявата ѝ страна, а всички елементи, по-големи от оста са отдясно. Наричаме тази процедура разделяне. В този момент няма значение как са подредени един спрямо друг елементите от лявата страна на оста. Същото важи и за елементите отдясно. Интересува ни само това всеки елемент да е от правилната страна.
В практиката винаги избираме за ос най-десния елемент от подмасива array[r]. Например ако подмасивът се състои от [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], избираме за ос числото 6. След разделянето, подмасивът изглежда така [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Нека q е индексът на оста.
Завладяваме, като рекурентно сортираме подмасивите array[p..q-1] (всички елементи вляво от оста, които трябва да са по-малки или равни на оста) и array[q+1..r] (всички елементи вдясно от оста, които трябва да по-големи от оста).
Комбинираме без да правим нищо. След като приключи стъпката с рекурентно сортиране, сме готови. Защо? Всички елементи отляво на оста в array[p..q-1] са по-малки или равни на оста и са сортирани, а всички елементи отдясно на оста в array[q+1..r], са по-големи от нея и са сортирани. Няма как елементите в array[p..r] да не са сортирани!
Помисли за нашия пример. След рекурентното сортиране на подмасивите отляво и отдясно на оста, подмасивът отляво на оста е [2, 3, 5], а подмасивът отдясно на оста е [7, 9, 10, 11, 12, 14]. Така подмасивът съдържа [2, 3, 5], следвано от 6, следвано от [7, 9, 10, 11, 12, 14]. Подмасивът е сортиран.

Основните случаи са подмасиви от по-малко от два елемента, както е в сортирането чрез сливане. В сортирането чрез сливане никога не използваш подмасив без елементи, но това е възможно в бързото сортиране, ако всички елементи в подмасива са по-малки или равни на оста, или са по-големи от оста.

Да се върнем на стъпката "владей" и да минем през рекурентното сортиране на подмасивите. След първото разделяне имаме подмасивите [5, 2, 3] и [12, 7, 14, 9, 10, 11] и ос 6.

За да сортираме подмасива [5, 2, 3], избираме за ос 3. След разделянето имаме [2, 3, 5]. Подмасивът [2], отляво на оста, е основен случай за рекурсията, както е и подмасивът [5] отдясно на оста.

За да сортираме подмасива [12, 7, 14, 9, 10, 11], избираме за ос 11, което дава [7, 9, 10] отляво на оста и [14, 12] отдясно. След сортирането на тези подмасиви имаме [7, 9, 10], следвано от 11, следвано от [12, 14].

Ето как протича алгоритъмът на цялото бързо сортиране. Позициите в масива в синьо са били оси в предишни рекурентни извиквания и затова стойностите на тези позиции няма да бъдат разгледани или преместени:

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.