Algoritmi za urejanje podatkov

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

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

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

Č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

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

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.