Ogled vira Algoritmi za urejanje podatkov

'''Algoritem za urejanje podatkov''' ali '''algoritem za sortiranje podatkov''', je v [[Računalništvo|računalništvu]] [[algoritem|postopek]], s katerim elemente [[Seznam (računalništvo)|seznama]] uredimo po določenem vrstnem redu. Rezultat urejanja je urejen seznam, ki je [[permutacija]] elementov vhodnega seznama.

== Delitve algoritmov za urejanje ==

Lahko jih delimo glede na to, kakšne sezname urejajo (numerični, leksikografski), glede na to, kje med urejanjem hranimo podatke (notranji in zunanji), glede na [[Časovna zahtevnost|časovno]] ali [[prostorska zahtevnost|prostorsko zahtevnost]], glede na princip urejanja (z zamenjavami, z vstavljanjem, s porazdelitvami, z zlivanjem, z urejanem po delih) in glede na nekatere lastnosti, kot je npr. stabilnost in zmožnost urejanja iz toka podatkov.

== Notranji algoritmi za urejanje ==

Notranji algoritmi za urejanje hranijo vse potrebne podatke ves čas urejanja v glavnem pomnilniku računalnika.

Nekaj algoritmov za notranje urejanje:

* [[hitro urejanje]] (ang. ''QuickSort'')
* [[urejanje z zlivanjem]] (''MergeSort'')
* [[urejanje s kopico]] (''HeapSort'')
* [[Shellovo urejanje]] (''Shell Sort'')
* [[urejanje z navadnim vstavljanjem]] (''Insertion Sort'')
* [[urejanje z navadnim izbiranjem]] (''Selection Sort'')
* [[mehurčno urejanje]] (''Bubble Sort'')
* [[urejanje po delih]] (''Radix Sort'')

== Zunanji algoritmi za urejanje ==

Zunanji algoritmi berejo dele podatkov z zunanjega pomnilnika in jih urejajo v več stopnjah. Uporabljamo jih, kadar urejamo sezname, ki so preveliki za glavni pomnilnik, ki ga imamo na voljo.

Za zunanje urejanje lahko uporabimo [[navadno zlivanje|urejanje z zlivanjem]] ali katero izmed izpeljank, kot sta [[naravno zlivanje|urejanje z naravnim zlivanjem]] in [[Polifazno urejanje|urejanje s polifaznim zlivanjem]].

== Časovna zahtevnost ==
{{glavni|časovna zahtevnost}}

Preprosti algoritmi za urejanje, ki so se pojavili med prvimi (mehurčno urejanje, urejanje z navadnim vstavljanjem, urejanje z navadnim izbiranjem), imajo v povprečju časovno zahtevnost <math>O(n^2)</math>. Prvi algoritem, ki je to mejo nekoliko znižal je Shellovo urejanje, ki je nadgradnja navadnih vstavljanj v več stopenj. Njegova časovna zahtevnost je zelo odvisna od stopenj, ki jih izberemo za urejanje in v splošnem ni znana, je pa navzgor omejena z <math>O(n^2)</math>. Hitro urejanje, urejanje z zlivanjem in urejanje s kopico pa imajo v povprečju časovno zahtevnost <math>O(n \log n)</math>. To je tudi teoretična spodnja meja za algoritme, ki uporabljajo primerjave in zamenjave. Urejanje po delih ({{jezik-en|Radix sort}}) in nekateri drugi algorimi za urejanje, pa imajo teoretično spodnjo mejo <math>O(n)</math>, a niso primerni za vse tipe vhodnih podatkov.

== Prostorska zahtevnost ==

Za algoritme, ki ne zahtevajo dodatnega prostora v pomnilniku pravimo, da urejajo na mestu in imajo prostorsko zahtevnost <math>O(1)</math>. Algoritmi kot je npr. urejanje z zlivanjem, pa pri urejanju potrebujejo dodaten prostor takšne velikosti, kot ga zaseda vhodni seznam. Za take algoritme pravimo, da imajo prostorsko zahtevnost <math>O(n)</math>.

== Stabilnost ==

Algoritem za urejanje podatkov je stabilen, kadar ohranja vrstni red enakih elementov. Ta lastnost je uporabna, kadar urejamo nek seznam elementov po več kriterijih - če na primer uredimo nek seznam po abecedi, nato pa po datumu, bodo elementi z istim datumom še vedno urejeni tudi po abecedi. [[Urejanje z zlivanjem]] in [[urejanje z navadnim vstavljanjem]] sta stabilna algoritma.

[[Kategorija:Algoritmi]]
[[Kategorija:Algoritmi za urejanje podatkov| ]]