Основно съдържание
Компютърни науки
Курс: Компютърни науки > Раздел 1
Урок 9: Бързо сортиранеПреглед на бързо сортиране
Подобно на сортиране чрез сливане, бързото сортиране използва "разделяй и владей" и затова е рекурсивен алгоритъм. Бързото сортиране използва "разделяй и владей" по по-различен начин от сортирането чрез сливане. В сортирането чрез сливане стъпката за разделяне не прави почти нищо, а цялата реална работа се извършва в стъпката комбиниране. При бързото сортиране е обратното – реалната работа се извършва в стъпката "разделяй". Всъщност стъпката "комбинирай" в бързото сортиране не прави абсолютно нищо.
Има още няколко разлики между бързо сортиране и сортиране чрез сливане. Бързото сортиране работи на място. А най-лошото му време за изпълнение е като това на сортирането с пряка селекция и с вмъкване: \Theta, left parenthesis, n, squared, right parenthesis. Но средното време за изпълнение е като при сортиране чрез сливане: \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis. Защо тогава да мислим за бързо сортиране, щом сортирането чрез сливане е поне толкова добро? Това е така, защото константата, скрита в нотацията Θ за бързото сортиране, е доста добра. В практиката бързото сортиране превъзхожда сортирането чрез сливане и значително превъзхожда пряката селекция и сливането.
Ето как бързото сортиране използва "разделяй и владей". Както при сортирането чрез сливане, помисли за сортиране на подмасива
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.
Искаш ли да се присъединиш към разговора?
Все още няма публикации.