Uspori malo !!!!!!!!!!
Biranje srednje vrednosti daleko je od pravog resenja, osim ako se radi o prilicno velikom nizu sa nekom pravilnom raspodelom (uniformnom, gausovom, ...) a takvi idealni slucajevi su prilicno retki.
Posmatrajmo recimo niz:
1 1 1 2 3 3 3 15 100 (napisao sam sortirano zbog lakse ilustracije)
Suma = 129
Srednja vrednost = 129 / 9 = 14,3333...
Najblizi clan je 15
Da li on deli niz na dva podniza priblizne duzine ??? Nikako !
Resenje sa 2 prolaza se moze naci a pri tom treba korisiti i neku dodatnu memoriju.
Ako su u pitanju brojevi, a nije obavezno koristiti Quick Sort mogu ti predloziti sort u O(n) koji zahteva dodatno koriscenje memorije.
Svima je poznato ono prosto prebrojavanje i tzv. linearni sort : npr. imas 1000000 clanova niza (brojeva) ali su svi clanovi celi recimo od 1 do 1000. Kreiras niz od 1000 clanova, prodjes jednom i prosto ih prebrojis i posle prolazom od 1000 mozes sve da ih prikazes ili sta vec sortirane.
Moja ideja (radi i za stringove, ili bilo koji "nizom opisive" strukture podataka), inace se zasniva na prebrojavanju:
Primere cu pisati pascalom, obzirom da skoro svi razumeju.
Formiras sledecu strukturu
Code:
type TChild = ^node;
node = Record
Count : Integer;
Child : array [0..9] of TChild;
End;
var root : TChild;
Ovo je primer za stabaoce gde se brojevi pamte po svojim ciframa. Inace moguce je raditi i binarnom predstavom radi dobijanja binarnog stabla (u tom slucaju sortiranje prestaje da bude linearno i prelazi u O(n*log n), ali radi UVEK u toj slozenosti - dakle eliminise problem Quick Sort-a oko odabira pivota).
Najpre je svaki clan potrebno dodati u stablo: Broj prolaza je n * prosecna_duzina_podatka gde je n broj clanova niza a navedena duzina je duzina podatka (npr. ako se radi sa ciframa kao u primeru to je prosecan broj cifara, a ako se radi sa binarnom predstavom to je prosecno logaritam podatka za osnovu dva.
Dakle ovo je brze resenje, ali memorijski zahtevnije jer za svaki kreirani nod slocira memoriju za 10 potencijalnih naslednika umesto za dva).
Dodavanje se vrsi jednostavno. U ovom slucaju rastavimo broj na cifre (sto je trivijalno) i nadjemo njegovu poziciju u stablu (prosetamo se od root-a). Zavisnost od duzine podatka upravo odavde potice. Ako negde dodjemo na nil u lociranju, onda kreiramo taj clan i sve sto kreiramo postavljamo na count=0 (to je broj pojavljivanja). Kada na kraju dodjemo do pozicije naseg clana imamo dva slucaja:
1. Dosli smo do ove pozicije prvi put - dakle samo alociramo memoriju i postavimo njegov Count na 1.
2. Vec je kreirana putanja do ovog clana - povecamo Count za 1.
Sta smo dobili ?
Ocitavanjem stabla (koje je O(n)) na taj nacin sto krenemo od root-a i prvo citamo Count roditelja, a zatim pretrazimo sve njegove naslednike mozemo ispisati (ili sta vec) sortiran polazni niz. I to je cela filozofija.
Dakle algoritam je ultra jednostavan, a ono na sta treba obratiti paznju je na koji nacin planiramo da organizujemo strukturu i to zavisi iskljucivo od toga sta sortiramo. Recimo za sortiranje reci mogla bi se koristiti sledeca stukrura:
Code:
type TChild = ^node;
node = Record
Count : Integer;
Child : array ['A'..'Z'] of TChild;
End;
var root : TChild;
Da stvar bude jasnija ovo je samo uopstena varijanta onog prostog prebrojavanja (prvo navedeno) koja omogucava da sami odredjujete odnos brzina / koriscenje memorije zavisno od podataka kojima baratate. Recimo navedeni primer sa brojevima iz opsega od 1 do 1000 se moze predstaviti vrlo jednostavno:
Code:
type TChild = ^node;
node = Record
Count : Integer;
Child : array [1..1000] of TChild;
End;
var root : TChild;
Sto se tice polaznog pitanja o pivotu razmislicu o tome stvarno se davno nisam patio sa sortovima tipa Quick, ali mozda vredi razmotriti i opisanu ideju.
Ziveli !