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 . 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 . Hitro urejanje, urejanje z zlivanjem in urejanje s kopico pa imajo v povprečju časovno zahtevnost . To je tudi teoretična spodnja meja za algoritme, ki uporabljajo primerjave in zamenjave. Urejanje po delih () in nekateri drugi algorimi za urejanje, pa imajo teoretično spodnjo mejo , 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 . 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 .

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.

Algoritmi
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 \ . 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 \ . Hitro urejanje , urejanje z zlivanjem in urejanje s kopico pa imajo v povprečju časovno zahtevnost \ . To je tudi teoretična spodnja meja za algoritme , ki uporabljajo primerjave in zamenjave . Urejanje po delih ( ) in nekateri drugi algorimi za urejanje , pa imajo teoretično spodnjo mejo , 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 \ . 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 \ . 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 . Algoritmi