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

Бързо сортиране - много ефективен алгоритъм и е известен като средно най-бързият алгоритъм за сортиране с общо предназначение. Бързото сортиране сравнява всички елементи на масива с един, почти на случаен принцип, елемент (pivot) и по този начин разделя масива на две части - едната съдържа числа, по-малки от pivot, а другата - bотноснонай-основните. След това всяка от тези две части също се подлага на подобно сортиране и така докато следващата част се окаже съставена от един елемент.

По този начин quicksort е рекурсивен алгоритъм, т.е. алгоритъм, който се самоизвиква. Времето за бърза сортировка е пропорционално на n * log (n). Има обаче недостатъци на алгоритъма за бърза сортировка. Масив от произволни числа се сортира много бързо, но новосъртиран масив може да бъде преработен чрез процедурата изключително бавно, до пълното изчерпване на капацитета на стека, тъй като ефективността на алгоритъма зависи силно от успешния избор на шарнирния елемент.

Тук е интересен методът за разделяне на масива спрямо ос. За това се използват два противоположно насочени процеса. Първият започва от началото на масива и търси елемент, по-голям от ос. Вторият започва от края и търси елемента, по-малък от ос. Веднага щом се намерят такива елементи, местата им се разменят и след това търсенето продължава от мястото, където процесите са спрели.

По този начин, когато процесите се срещнат - това се случва някъде в средата на масива - всеки елемент в първата част е по-малък от основния, а във втората - повече. Тоест, всеки елемент в първата част е по-малък от всеки във втората. Това означава, че няма нужда да ги сравнявате помежду си. Остава само да се извърши една и съща операция по отношение на тези две половини и така нататък, докато един елемент остане в следващата част на масива, което означава, че масивът е сортиран.

Най-добрият избор за ос е средният елемент в масива. Следователно трябва да изберете пивотен елемент със среден индекс. Това минимизира вероятността за най-лошия избор - най-малкия елемент в масива. Още по-добре е да изберете елемента със средна стойност от елементите с първи, последен и среден индекс като пивот.

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

Ето внедряването на алгоритъма за бързо сортиране в Delphi:

Тип Масив: Масив от Цяло число; // Параметрите на масива трябва да бъдат дефинирани преди извикване на процедурата

процедура qSort (var A: TArray; min, max: Integer);
вар i, j, supp, tmp: Цяло число;
започнете
supp: = A [max - ((max-min) div 2)];
i: = мин; j: = max;
докато аз вечерям направете j: = j-1;
ако i

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

qSort (A, 0, High (A)); // 0 - начален индекс, High (A) - краен индекс на масив A