Бързото сортиране като техника за програмиране
През 1960 г. C. A. Hoare разработва най-известния метод за бързо сортиране. Днес той се използва широко в програмирането, тъй като има много положителни свойства: може да се използва за общи случаи, изисква малко увеличение на допълнителна памет, съвместим е с различни видове списъци и е удобен за изпълнение. Но има и недостатъци, които Quicksort има: когато се използва в работата, се правят много грешки и е донякъде нестабилен.
Това обаче е най-проучваната версия. След появата на първите изчисления на Хоар мнозина започнаха да го изучават внимателно. Създадена е голяма база върху теоретичните въпроси за намиране на времето, прекарано на работа, което е подкрепено с емпирични данни. Имаше реални предложения за подобряване на основния алгоритъм и увеличаване на скоростта на работа.
Quicksort е много разпространено и може да се намери навсякъде. Въз основа на него е реализиран методът TList.Sort, който съществува във всички версии (с изключение на 1) на Delphi, функцията на библиотеката за изпълнение, qsort в C++.
Основният принцип на работа може да се формулира като „разделяй и владей“. Списъкът е разделен на две групи и сортирането се извършва за всяка част самостоятелно. От това следва, че трябва да се обърне повече внимание на процеса на разделяне, по време на който се случва следното: определя се основният елемент и целият списък се пренарежда спрямо него. Отляво се подрежда група кандидати, чиито стойности са по-малки, отдясно се прехвърлят всички останали. Оказва се, че основният елемент в сортирания списък се намира на полагащото му се място. Следващата стъпка е да извикате функцията за рекурсивно сортиране от двете страни на елементите спрямо основния. Работният процес приключвасамо когато списъкът ще съдържа само един елемент, тоест ще бъде сортиран. По този начин, за да овладеете такава програмна функция като бързо сортиране, трябва да знаете работата на алгоритми от по-ниско ниво: а) избор на основен елемент; б) най-ефективната пермутация на списъка за получаване на две групи с по-малки и по-големи стойности.
Нека се запознаем с принципите на първия. Когато избирате основен елемент, в идеалния случай трябва да изберете средния елемент от списъка. След това, когато се счупи, ще се раздели на две равни половини. Самото изчисляване на средната стойност в списъка е много трудно, така че дори най-бързото сортиране заобикаля това изчисление. Но изборът на основния елемент с максимална или минимална стойност също не е най-добрият вариант. В случай на такава дефиниция, единият от създадените списъци е гарантирано празен, а вторият е препълнен. Оттук и заключението, че като основен елемент трябва да се избере този, който е по-близо до средното, но по-далеч от максимума и минимума.
След като направите избора, можете да продължите към работата на алгоритъма за разделяне. Това са така наречените вътрешни цикли на бързото сортиране. Всичко е изградено на два бързи индекса: първият ще премине през елементите отляво надясно, вторият, напротив, отдясно наляво. Започва операцията за изпълнение отдясно: индексът преминава през списъка и сравнява всички стойности с основната. Цикълът се счита за завършен, ако има елемент по-малък или равен на основния. Тоест възниква сравнение и стойността на индекса намалява. От лявата страна работата е завършена, когато се намери по-голяма или равна стойност. И тук стойността се увеличава при сравнение.
На този етап от алгоритъма за разделяне, който съдържа бързо сортиране, могат да възникнат две ситуации. Първият ече индексът отляво ще бъде по-малък от този отдясно. Това показва грешка, тоест посочените елементи са в грешен ред в списъка. Изходът е да ги размените. Втората ситуация е, когато и двете колони са равни или се пресичат. Това показва успешно разделяне на списъка, тоест работата може да се счита за завършена.