Hitro urejanje: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m [r2.6.4] robot Dodajanje: lv:Ātrās kārtošanas algoritms |
Brez povzetka urejanja |
||
Vrstica 2:
'''Hitro urejanje''' ali '''urejanje s porazdelitvami''' ({{jezik-en|'QuickSort'}}) je eden od najbolj znanih in uporabljanih [[Algoritmi za urejanje podatkov|algoritmov za urejanje podatkov]]; razvil ga je [[C. A. R. Hoare]].
[[Algoritem]] razdeli zaporedje na dve podzaporedji tako, da
== Delovanje ==▼
Zaporedje razdelimo na podzaporedji tako, da izberemo nek [[delilni element]] ({{jezik|en|''pivot''}}) iz zaporedja, nato pa zaporedje pregledujemo z leve in desne strani. Levi indeks povečujemo, dokler ne naletimo na element, ki je večji ali enak
Postopek delitve nato [[rekurzija|rekurzivno]] ponovimo nad podzaporedjema, pri čemer podzaporedji ne vsebujeta delilnega elementa, saj je le-ta že na pravilnem mestu na sredini med njima.
Ko pridemo do podzaporedij dolžine ena, je celotno zaporedje urejeno.
== Izbiranje delilnega elementa ==
Z dobro izbiro delilnega elementa lahko preprečimo, da bi se zgodil najslabši primer in bi algoritem potreboval <math>O(n^2)</math> operacij.
*
Največkrat uporabljani delilni elementi so:
* prvi element
* zadnji element
* naključno izbran element
* sredinski element ali mediana
▲== Delovanje ==
▲Zaporedje pregledujemo z leve in desne strani. Levi indeks povečujemo, dokler ne naletimo na element, ki je večji ali enak od delilnega. Zatem zmanjšujemo desni indeks, dokler ne naletimo na element, ki je manjši ali enak od delilnega elementa. Ko naletimo na takšna elementa in se indeksa ne prekrižata, zamenjamo položaj teh dveh elementov. Kadar pa sta se prekrižala pa zamenjamo desni indeks z mejnim elementom in rekurzivno kličemo proceduro HitroUredi.
== Zahtevnost ==
| |||