Бързо сортиране като метод за програмиране

През 1960 г. К. А. Хоре разработи метод за бързо сортиране на информация, която стана най-известната. Днес тя се използва широко в програмирането, тъй като има много положителни свойства: тя може да се използва за общи случаи, изисква малко увеличение на допълнителната памет, е съвместима с различни видове списъци и е удобна за внедряване. Но има и недостатъци, които бързо сортиране има: когато се използва в работата, много грешки са позволени и това е до известна степен нестабилна.

Това обаче е най-проучената версия. След появата на първите изчисления на Хоар, много от тях се занимаваха с гъстото си изследване. Създадена бе голяма база по теоретичните въпроси за намиране на време за работа, което беше подкрепено от емпирични данни. Имаше реални предложения за подобряване на основния алгоритъм и за увеличаване на скоростта на работа.

Бързото сортиране е много често, може да се намери навсякъде. Тя се основава на метода TList.Sort, който съществува във всички версии (с изключение на 1) на Delphi, функцията на библиотеката за времето, прекарано в изпълнението, qsort в C ++.

Основният принцип на работа може да бъде формулиран като "разделяне и завладяване". Съществува разбивка на списъка в две групи и сортирането се извършва за всяка отделна част. От това следва, че трябва да се обърне повече внимание на процеса на разделяне, при който се получава следното: основният елемент се определя и целият списък вече се измества спрямо него. Група от кандидати се формира отляво, стойностите на които са по-малки, всички останали се прехвърлят надясно. Оказва се, че основният елемент в списъка за сортиране се намира на правилното му място. Следващата стъпка е да се извика рекурсивната функция за сортиране за двете страни на елементите спрямо базата. Процесът на работа завършва само когато списъкът съдържа само един елемент, т.е. той ще бъде сортиран. По този начин, за да се овладее такава функция за програмиране като бързо сортиране, трябва да знаете работата на алгоритми от по-ниско ниво: а) изборът на базовия елемент; б) най-ефективната пермутация на списъка за получаване на два комплекта с по-малки и по-големи стойности.

Ще се запознаем с принципите на първия. При избора на основен елемент в идеалния случай средният трябва да бъде избран от списъка. Тогава, когато се счупи, се разделя на две равни половини. Само изчисляване средна стойност в списъка е много трудно, така че дори най-бързото сортиране заобикаля това смятане отстрани. Но изборът на основен елемент с максимална или минимална стойност също не е най-добрият вариант. В случай на такава дефиниция един от създадените списъци ще бъде гарантиран като празен, а вторият ще бъде препълнен. Оттук и заключението, че като основен елемент трябва да се избере една, която е по-близо до средната, но по-далеч от максималната и минималната.

След като сте решили за избора, можете да продължите към работата на алгоритъма за разделяне. Това са така наречените вътрешни цикли на бързо сортиране. Всичко е изградено върху два бързо работещи индекси: първият ще се избира от елементи от ляво на дясно, а вторият - от дясно на ляво. Изпълнява се операцията за изпълнение вдясно: индексът минава през списъка и сравнява всички стойности с основния. Целият цикъл се счита за завършен, ако има елемент, по-малък или равен на базовия. Това означава, че стойността на индекса се сравнява и намалява. От лявата страна работата завършва, когато се намери по-голяма или еднаква стойност. И тук стойността на сравнението се увеличава.

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