>BTW: vprasanje za ostale (ker nimam prevec pojma o sortirnih
>algoritmih), tisti zgoraj bo rabil N^2 prehodov (pri N podatkih). A mi
>lahko kaksen FRIjevec pove, koliko prehodov bi naredil, ce bi v i-tem
>prehodu od spodnje meje do zgornje meje (i .. max_k) poiskal
>najnizjo/najvisjo vrednost in jo zamenjal s i-to ter sel na naslednji i
>?? En tak banalen popravek .. Nekako se mi zdi, da pol manj (ja ?),
>nisem pa 100% preprican. Tale ekonomija mi unicuje mozgane .. :->
Sicer ne hodim se na FRI, ampak ok.
To kar ti opisujes je "Selection sort" algoritem.
Ta v splosnem za N elementov rabi N^2 / 2 primerjav in N zamenjav.
(vse te stvari so lepo razlozene v knjigi "Robert Sedgewick: Algorithms in
C++")
Res pol manj, ja.
Podobno je tud z "Insertion sort"-om. Najvec tu porabimo za prestavljanje
dela arraya
(tako da lahko element "vrinemo" na pravilno mesto).
"Shell sort" dela s kompleksnostjo N ^ (3/2).
Deluje podobno kot prejsnja zadeva le da primerja med seboj bolj oddaljene
elemente.
Sicer odvisno od podatkov - ampak do sedaj najbolsa stvar je "Quick sort".
(2N lgN )
V podatkih najdes en t.i. "partition" element, ki naj bi bil v idelnem
primeru ravno element po velikosti
nekje na sredini med vsemi ostalimi elementi. Potem pa zmeces vse elemente,
ki so vecji od tega
"partition" elementa na eno stran, manjse pa na drugo.
Nato vsako od obeh strani rekurzivno enako sortiras naprej.
Edino za malo elementov se izkaze, da delajo drugi sortirni algoritmi
bolje, tako da v takem primeru
raje kot da bi kar naprej klical "quick sort" nad takim delckom poklices
"shell sort".
c'ya,
fiction
