[ --SOULMaTe-- @ 04.01.2004. 21:08 ] @
Maso, treba mi neki sajt ili bilo sta sto sadrzi algoritme za "pametno" biranje pivota prilikom sortiranja nekog niza. Hvala unapred.
[ passby @ 09.01.2004. 18:30 ] @
zar se sortiranje ne vrsi prema zadanom ?! , a zadano nam nisi dao ! niz cega...pivotiralo bi sto...
[ filmil @ 09.01.2004. 18:38 ] @
Rekao bih da je OP mislio na izbor referentne ćelije za quicksort.

f
[ passby @ 09.01.2004. 18:48 ] @
ma whatever, nisam u tim vodama-sorry
[ --SOULMaTe-- @ 11.01.2004. 02:33 ] @
Pa kod Quicksorta pre sortiranja u svakom pod nizu biramo element koji se naziva pivot i sve elemente manje od njega stavljamo levo od pivota, a sve vece od njega desno od pivota. E sad fora je izabrati takav pivot da otprilike pola elemenata bude vece od njega a pola manje, a u vremenu O(n).

Eto na to sam mislio. To je valjda i filmil rekao. :)
[ -zombie- @ 11.01.2004. 16:04 ] @
hmm.. zanimljivo problemče. ;)

prvo što pada na pamet je recimo da se nađe prosečna vrednost tih elemenata niza (suma/n), i da se onda nađe element koji je najbliži tom proseku. za ovo je potrebno dva prolaza, prvi za računanje sume, i drugi za nalaženje najbližeg elementa, ali to je opet O(2*n)=O(n).

naravno, ovo neće uvek davati element koji je tačno na polovini, ali u opštem slučaju će dati približno rešenje, ne?


jel postoji neka bolja ideja?
[ chupcko @ 11.01.2004. 16:59 ] @
Koliko se ja secam nekih analiza, stvarno je najbolje naci vrednost takvu da pola elemenata bude manje a pola vece, znaci neophodno je naci vrednosto koja je najbliza srednjoj vrednosti.

Naravno takva potraga zna da potraje.

Obicno ljudi uzimaju prvi element ili element na samo sredini niza (po indeksu). Tako ne trosimo vreme na izbor, a u najgorem slucaju (specijalno napakovan niz) imamo o(n^2).

E sada, moj zakljucak je da ako se ocekuju neki specijalno napakovani nizovi onda ... a ako ne onda ...
A u opstem slucaju najbolje je da uzmes random (ne ti Vrzo).
[ --SOULMaTe-- @ 11.01.2004. 17:11 ] @
Citat:
-zombie-:
hmm.. zanimljivo problemče. ;)

prvo što pada na pamet je recimo da se nađe prosečna vrednost tih elemenata niza (suma/n), i da se onda nađe element koji je najbliži tom proseku. za ovo je potrebno dva prolaza, prvi za računanje sume, i drugi za nalaženje najbližeg elementa, ali to je opet O(2*n)=O(n).

naravno, ovo neće uvek davati element koji je tačno na polovini, ali u opštem slučaju će dati približno rešenje, ne?


jel postoji neka bolja ideja?


Fino je to al to su opet dva prolaza a ja bi sa jednim . :)

Jedino da uzmem recimo prvi, srednji i poslednji clan pa onda nek bude pivot srednji po vrednosti od njih. Ili 3 random broja pa srednji od njih, al opet gubim vreme na odredjivanje random brojeva.
Chupko dovoljno mi je da je niz vec sortiran, sto nije tako tesko da se desi i teorija sa prvim clanom puca. Zato je ipak mozda najbolje uzeti onako prvi, srednji i poslednji, posto neki pametniji alogritam u O(n) ocigledno ne postoji. :)
[ Milos Stojanovic @ 11.01.2004. 18:46 ] @
Hmmm... da li su toliko glomazni podaci da je 2*n prolaza previše?
Koliko se ja sećam mojih predavanja o tehnikama sortiranja u 95% slučajeva je najbolje izabrati član random indexa kod korišćenja quicksorta
Ako ti treba za neke specijalne namene, kaži u čemu je stvar pa možda mogu nešto više da pomognem...
Možda ti HeapSort više odgovara ? ;)
[ -zombie- @ 11.01.2004. 20:26 ] @
Citat:
--SOULMaTe--:
Fino je to al to su opet dva prolaza a ja bi sa jednim . :)


pa pazi, praktično, ovo će biti duplo sporije nego O(n), ali se u teoriji to posmatra kao rešenje komplexnosti O(n)..

Citat:
Ili 3 random broja pa srednji od njih, al opet gubim vreme na odredjivanje random brojeva.


da, zanimljivo rešenje, i da si rekao da želiš komplexnost manju od O(n), i ja bi razmišljao nešto u tom pravcu. samo ne znam koliko će to značajno bolje raditi od prostog odabira jednog random broja (ne da mi se nešto da izračunam verovatnoće), dok fixno odabiranje nekog člana (pa čak i srednjeg od 3 fixno odabrana) treba izbegavati zbog mogućeg pakovanja..

Citat:
e sad, prvo mali uvod za one koji možda ne znaju taj fazon. zadatak otprilike glasi:

imate magnetnu traku (niz) sa milion realnih brojeva. operacija čitanja jednog broja traje jednu sekundu, i operacija premotavanja na proizvoljni broj traje isto jednu sekundu. izlaz vašeg programa treba da bude broj od koga je manje bar pola brojeva, tj broj, koji kada bi se brojevi sa trake (niz) poređali u rastućem poretku, bio "desno" od sredine niza.

naravno, program treba da nalazi takav broj za što kraće vreme.

rešenje se svodi na čitanje N (recimo 20) slučajno odabranih brojeva i štampanja najvećeg od njih. program troši samo 40 sekundi, a verovatnoća da odštampani broj odgovara zahtevima je 99.9999% (lako se dokazuje da je verovatnoća greške 1/2N).

naravno, za ovakvo rešenje možemo samo da tvrdimo da je vrlo verovatno tačno, ali ne i da garantujemo da jeste, pa zato nije uvek primenjivo, ali za naš problem traženja pivota očigledno da jeste, jer se ništa strašno neće desiti ako pogrešimo..


dakle, taj isti princip možemo primeniti i na naš problem traženja pivota. recimo, ako treba naći dobrog pivota u nizu od 1000 brojeva, dovoljno dobro bi bilo da odaberemo slučajno 10tak brojeva (log21000), i da nađemo srednji element među njima.

nažalost, sada opet rekurzivno dolazimo do istog problema, samo na manjem uzorku. opet treba što "pametnije" naći srednji elemenat tog novog niza od 10 elemenata :-P

na sreću, sada bar elemenata nema puno, pa možemo da primenimo i neki ne-tako-savršeni algoritam, recimo moj prvi predlog komplexnosti O(2*n).

a fazon je i što za drugi prolaz ne moramo da pamtimo kojih smo to 10tak elemenata izabrali u prvom prolazu (jer bi to značilo pravljenje privremenih nizova i komplikovanje algoritma), već možemo jednostavno nasumično odabrati novih 10tak elemenata, i naći onaj koji je najbliži proseku. i ako pretpostavimo da je funkcija rand() komplexnosti O(1), kao što uglavnom danas jesu, ovo će verovatno ispasti prilično brz algoritam.

dakle, uz mnogo pretpostavki, i vrlo malo dokaza, imam osećaj da tvrdim da je ovo prilično "pametan" način za nalaženje pivota niza. evo ga i u pseudokodu: (pošto verovatno nisam baš najrazumljivije objasnio ;)

Code:

function nađi_pivot_niza(niz, dužina)   
    uzorak = log2(dužina)
    zbir = 0
    for i in 1..uzorak
        k = rand(dužina)
        zbir = zbir+niz[k]
    end for
    prosek = zbir/dužina
    element = 0
    for i in 1..uzorak
        k = rand(dužina)
        if abs(niz[k]-prosek)<abs(niz[element]-prosek)
            element = k
        end if
    end for
    return element
end function

[ dRock9 @ 12.01.2004. 14:54 ] @
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 !
[ -zombie- @ 12.01.2004. 22:10 ] @
Citat:
dRock9:
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)


upravo suprotno. baš je najviše nizova sa nekom vrstom "uniformne" raspodele, a ovo što ti daješ za primer spada u "specijalne slučajeve".

uzmi na primer generiši slučajno hiljadu nizova od po sto elemenata, i videćeš da algoritam sa srednjom vrednošću daje prilično dobar rezultat u priličnom broju slučajeva. pod time podrazumevam grešku do 5 elemenata (5%), u bar 90% slučajeva, što je prilično upotrebljivo za problem nalaženja pivota.

znači, poJenta je dati rešenje koje dovoljno često daje dovoljno dobar rezultat. znači praktično, a ne raspravljati u teoriji ŠBBKBB.


a ovo drugo što predlažeš je vrlo usko specijalizovan algoritam za pretraživanje koji vrlo često ne zadovoljava potrebe (pada kod običnog sortiranja integera (32bit) i realnih brojeva), a i nema ama baš nikakve veze sa temom i problemom o kome je ovde reč.
[ --SOULMaTe-- @ 12.01.2004. 23:10 ] @
Citat:
dRock9:
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.


Pazi ako cu ja da radim na racun memorije, onda cu jednostavno uzeti Mergesort ili Heapsort :)

Inace hvala na ovolikom trudu dRock9 al mislim da si mozda malo odlutao od teme.


I sta onda zombie predlazes koristiti Median of three(srednji od 3 random broja) algoritam komplexnosti O(n) ili odredjivaje one aritmeticke sredine komplexnosti O(2*n) koji i nije bas tako pouzdan (mislim na primer koji je dRock9 naveo)?

Najverovatnije ce biti Median of Three :)
[ -zombie- @ 12.01.2004. 23:35 ] @
pa mislio sam da sam bio jasan (tj znao sam da nisam bio ;)

koristi ili "srednji od random tri", ili još bolje moj opisani "srednji od random log2N".
[ --SOULMaTe-- @ 13.01.2004. 10:16 ] @
Ok! Hvala vam svima na pomoci.
[ dRock9 @ 13.01.2004. 12:57 ] @
Sto se tice koriscenja memorije koristi je i Quick Sort (pogotovo ako radis rekurzivno).
Nisam znao da je u pitanju sort slucajno biranih brojeva (ili nekih koji se mogu predstaviti mekom finom raspodelom)

zombie:
Sto se tice samog algoritma koji sam naveo rekao sam da je potrebno prilagoditi, a ja sam samo naveo primer za sort integera. Algoritam se moze prilagoditi za sortiranje bilo kakvog tipa podataka deterministicke duzine u sta spada i racunarska predstava realnih brojeva.