Quicksort като метод за програмиране

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

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

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

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

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

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

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