Algoritmi za urejanje podatkov

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Algoritem za urejanje podatkov ali algoritem za sortiranje podatkov, je v računalništvu postopek, s katerim elemente seznama uredimo po določenem vrstnem redu. Rezultat urejanja je urejen seznam, ki je permutacija elementov vhodnega seznama.

Delitve algoritmov za urejanje[uredi | uredi kodo]

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 časovno ali 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[uredi | uredi kodo]

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

Nekaj algoritmov za notranje urejanje:

Zunanji algoritmi za urejanje[uredi | uredi kodo]

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 urejanje z zlivanjem ali katero izmed izpeljank, kot sta urejanje z naravnim zlivanjem in urejanje s polifaznim zlivanjem.

Časovna zahtevnost[uredi | uredi kodo]

Glavni članek: č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 O(n^2). 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 O(n^2). Hitro urejanje, urejanje z zlivanjem in urejanje s kopico pa imajo v povprečju časovno zahtevnost O(n \log n). To je tudi teoretična spodnja meja za algoritme, ki uporabljajo primerjave in zamenjave. Urejanje po delih (angleško Radix sort) in nekateri drugi algorimi za urejanje, pa imajo teoretično spodnjo mejo O(n), a niso primerni za vse tipe vhodnih podatkov.

Prostorska zahtevnost[uredi | uredi kodo]

Za algoritme, ki ne zahtevajo dodatnega prostora v pomnilniku pravimo, da urejajo na mestu in imajo prostorsko zahtevnost O(1). 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 O(n).

Stabilnost[uredi | uredi kodo]

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 naprimer 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.