Quicksort kao metoda programiranja

Godine 1960, K. A. uhvati razvio metodu za brzo sortiranje informacija, postao najpoznatiji. Danas je naširoko koristi u programiranju, jer ima puno pozitivnih osobina: on se može koristiti za opće slučajevima, to zahtijeva malo povećanje u dodatnom memorijom kompatibilan s različitim vrstama popisa i jednostavan za implementaciju. No, tu su nedostaci, koji ima quicksort: pomoću djelo dozvoljeno puno grešaka, a to je nešto nestabilno.

Međutim, to je najviše proučavao verzija. Nakon prvog plaćanja Hoare, mnogi to svoje guste studiju. velika baza osnovana na teoretskim pitanjima pronalaženja vrijeme provedeno na poslu, koja je utemeljena na empirijskim dokazima. Bilo je konkretnih prijedloga za poboljšanje osnovne algoritam i povećanu brzinu.

Quicksort je vrlo čest, može se naći posvuda. Na svojoj bazi metoda se provodi TList.Sort, prisutna u svim verzijama (osim 1) Delphi, knjižnice funkciji vremena koje je bilo potrebno za dovršetak, qsort u C ++.

Osnovni princip rada može se formulirati kao „podijeli pa vladaj”. To se događa razbijanje popis u dvije skupine te su razvrstani za svaki dio po sebi. Iz toga slijedi da više pozornosti treba posvetiti procesu separacije, u kojem se pojavljuje sljedeće: određuje bazna elementa, te je relativno preuredio cijeli svoj popis. Izgrađen s lijeve skupine kandidata, čija je vrijednost manja od svih drugih pravila prijenosa. Ispada da je glavni element u popisu poredani u mjesto koje joj pripada. Sljedeća faza - izazov rekurzivni sortiranje funkcije za obje strane elementa u odnosu na bazu. Završava proces funkcionira samo ako popis sadrži samo jedan element, koji treba sortirati. Stoga, kako bi se savladala programski funkciju kao brz vrste, potrebno je poznavati rad na nižoj razini algoritama: a) izbor osnovnog elementa; b) popis najučinkovitiji permutacije proizvoditi dva seta sa manjim i većim vrijednostima.

Upoznate s prvim načelima. Prilikom odabira baznog elementa, idealno bi trebao biti izabran s liste prosjeku. Tada se na pauzi je podijeljen u dvije jednake polovice. Samo izračunati prosječna vrijednost na popisu je vrlo teško, pa čak i najbrži sortiranje zaobilazi ovu kamenca stranu. No, izbor osnovnog elementa s maksimalnom ili minimalnom vrijednošću - također nije najbolja opcija. U slučaju da takav određivanje jednog stvara prazne liste će biti zajamčena, a drugi pun. Stoga je zaključak da je kao osnovnog elementa treba odabrati onaj koji je bliže prosjeku, ali na maksimumu i minimumu.

Kada se određuje izbor, možete nastaviti na algoritma dekompozicije. Ovaj takozvani unutarnjeg uški brzo sortirati. Sve je izgrađena na dvije brzi pristup indeksa: prvo ide preko elemenata od lijeva na desno, drugi, naprotiv, s desna na lijevo. Počinje izvršavanja operacija pravo: indeks je na listi i usporedite sve vrijednosti za glavna. Ciklus je završena kada je element je manji od ili jednak početku. To je, tu je usporedba i smanjuje vrijednost indeksa. Na lijevoj ruci kad se posao završi veća od ili jednaka vrijednost. Evo, usporedba povećava vrijednost.

U ovoj fazi particioniranje algoritma koji se sastoji quicksort, mogu nastati dvije situacije. Prvi je da je indeks na lijevoj strani je manje nego u pravu. To ukazuje na pogrešku, onda postoje elementi na kojima je navedeno u popisu u pogrešnom redoslijedu. Izlaz - promijeniti svoje mjesto. Druga situacija je kad oba stupca jednaka ili prešao. To ukazuje na uspješno razdvajanje popisa, to jest, posao je sada gotova.