Квиксорт као метод програмирања

Године 1960., К.А. Иње развио методу за брзо сортирање информација, постао најпознатији. Данас је у широкој употреби у програмирању, јер има много позитивних особина: може се користити за опште случајева, то захтева мало повећање додатне меморије, компатибилан са различитим врстама листа и лако да спроведе. Али постоје недостаци, који има квиксорт: користећи рад дозвољен много грешака, и то је донекле нестабилна.

Међутим, то је највише проучавали верзија. Након првог плаћања Хоаре, многи радити свој густ студију. велика база је основана на теоријским питањима проналажења време проведено на послу, који је подржана од стране емпиријских доказа. Било је прави предлози за побољшање основне алгоритам и повећање брзине.

Квиксорт је врло честа, може се наћи свуда. На основу њега се поступак спроводи ТЛист.Сорт, присутне у свим верзијама (осим 1) Делпхи, библиотеке функцији времена које је било потребно да се заврши, ксорт у Ц ++.

Основни принцип рада може се формулисати као "завади па владај". Јавља се разбијање листу у две групе и су поредани за сваки део по себи. Из тога следи да више пажње треба посветити процесу раздвајања, током којег долази следеће: одређује основну елементом и има релативно преуређен цео свој списак. Изграђена на левој страни групе кандидата, чија вредност је мања од свих других правила преноса. Испоставило се да је главни елемент у листи сортирани је у свом правом месту. Следећа фаза - изазов функције рекурзивни сортирање за обе стране елемената у односу на базу. То се завршава процес функционише само ако листа садржи само један елемент, који треба да се сортирају. Тако, да би се овлада функцију програмирања као брз врсте, неопходно је знати рад алгоритама нижег нивоа: а) избор дна; б) списак од најефикаснијих пермутације за производњу два сета са мањим и већим вредностима.

Упознати са основним принципима. Приликом избора члана базе, било би идеално да се изабере са листе просек. Затим на паузи је подељена на две једнаке половине. Само израчунати средња вредност у листи је веома тешко, па чак и најбрже сортирање заобилази овај каменца страну. Али избор основног елемента са максималним или минималне вредности - и није најбоља опција. У случају да ова одлука једног ствара празни листе ће бити загарантована, а друга пуна. Отуда и закључак да је, као припадник базне треба одабрати онај који је ближе просеку, али на максимум и минимум.

Када је избор одређује, можете да пређете на алгоритму декомпозиције. Овај такозвани унутрашњи петљи брзо врста. Све је изграђен на два брз приступ индекса: прво иде преко елемената са лева на десно, друга, напротив, са десна на лево. Почиње право извршавања операција: индекс на листи и упоредите све вредности главни. Циклус је потпуна када је елемент мања или једнака основној линији. То је, ту је поређење и смањује вредност индекса. На левој руци када се посао заврши већи или једнак вредности. Овде, повећава поређење вредност.

У овој фази алгоритма партиција која обухвата квиксорт, две ситуације могу настати. Први је да је индекс на левој страни је мање него у праву. Ово указује на грешку, онда постоје елементи на којима је наведено на листи су у погрешним редоследом. Излаз - мењају места. Друга ситуација је када оба колоне једнак или прешла. Ово указује на успешно раздвајање на листи, то јест, рад је сада завршен.