eh evo ovako, malo sam razmisljao i palo mi je na pamet sledece:
-moraces da 2 puta sortiras tvoj niz...

prvi put ga sortiras uz pomoc bublesort, quick sort ili koji vec volis
algoritam (da napomenem za buble sort, ako je prvi veci od
drugog zamenjuju se mesta itd... i sve tako do kraja niza..)da bi bilo
malo jasnije evo bublesort algoritma [primer za qbasic, s obzirom
da radis u paskalu]:




eh sad funkcija swap, ti zamenjuje sledece:

Bez pointera.
------------


Sa pointerima.
-------------




E sada drugo sortiranje
-----------------------



Da objasnim sta se u stvari desilo...
Imao si neki niz:

a[0] = 5;
a[1] = -5;
a[2] = 3.5;
a[3] = 0;


sortirani niz je us pomoc bublesorta:

a[0] = -5;
a[1] = 0;
a[2] = 3.5;
a[3] = 5;


Znaci:
clan 1 2 3 4
vrednost 1 2 3 4

a tebi treba a[0] >= a[1] <= a[2]....

clan 1 2 3 4
vrednost 2 1 4 3


Mozes sada jednostavno da zamenjujes clanovima mesta, nesto kao buble sort
samo da ti inkrementacija bude veca za jedan...razumes? dobro idemo polako:
znaci treba da menja mesta prvom i drugom clanu, pa zatim trecem i
cetvrtom itd...
kapiras?
napravi petlju...nemam sada vremena da ti i to radim, moram da
ucim redove... ma istrazuj...
Budi pozdravljen.

Samo je problem u tome što tvoj algoritam neradi u slučaju kad je broj članova niza neparan.

poz.

idi kroz niz i trazi najveci clan i zapamti indeks najveceg clana. onda zameni mesta sa prvim clanom niza. posle idi od drugog clana i trazi najmanji clan i onda zameni mesta sa drugim clanom niza....i tako dalje... a to da li traziz najmanji ili najveci mozes da kontrolises sa nekim boolean indikatorom koji se menja izmedju false i true. recimo na pocetku je p:=true a posle stavi p:=not p;

pa ok, mozes da isfreakombinujes da dodas jos jedan nulti clan niza...mada to ne bi bilo to, ali ajde sad...

Evo programa:


poz.

Ako ti josh uvek znaci odgovor na problem, obzirom da sam se tek registrovao, on ide ovako:

Tvoj problem je u programiranju opste poznat kao sortiranje niza u testerast sa zubom na prvom clanu (sa zubom na gore) - jer je prvi clan veci od drugog.

Sortiraj niz bilo kako (preporuka ukoliko je niz veliki je heap ili quick sort jer je slozenost O(n*log n)).
Pretpostavimo da je duzina niza n.
Zatim krenes od drugog clana niza nekim brojacem, pomeras se za dva i menjas ga sa clanom niza koji je od njega udaljen n/2 (ako je n neparan onda zaokruzi na +-1) dok clan kojim ga menjas (znaci brojac + round(n/2) ne dodje do n ili n+1, tj. >=n). Dobices gotov niz.
Ako ti neshto nije jasno, javi se na mail, pa cu ti poslati source (c, pascal, ...)

Nadam se da sam ti pomogao.

Posto je ovo nesto sto sam privatno izucavao prethodnih nekoliko meseci(i radio kao projekat za mlade talente), osecam se dovoljno strucnim da odgovorim...

Imas puno opcija...
Od jednostavnog exchange( O(n*n) ) i insertion ( O(n*n), sem u jednom specijalnom slucaju kada je linearan, i tada se fenomenalno koristi...) pa sve do budza zvanih heap, shell, quick,...

A ima jo boljih stvari...
Nisi mi rekao koliki je niz, tip clanova, opseg vrednosti clanova, etc...
Radim projekat (jos nije zavrsen) "inteligentnog" algoritma za sortiranje koji sam (ili uz malecnu pomoc) odredjuje koji ce tip algoritma da koristi, i ako je potrebno (ako vidi da je pogresio i/ili da se neki algoritam zaglavio i da tu drugi moze pomoci...) prebaci sortiranje ostatka niza na neki 2. tip sort alg....

[email protected]
UNDER CONSTRUCTION: http://solair.eunet.yu/~nanosoft

BlueIce:
Zanimljiva ti je ta ideja sa AI sortiranjem, mada tu i nema preterano mnogo filozofije. Skoro svaki od egzoticnih algoritama koji sortiraju u priblizno O(n*log n) ima svoj worst case i best case (najgori i najbolji slucaj) koji se obicno krecu izmedju O(n^2) i O(n). Pitanje je velicine nizova (ima li uopste svrhe praviti tako neshto za manje nizove, a za velike, ima li memorije).
Primera radi, ukoliko imas niz od milijardu clanova, sigurno neces raditi bubble sort, ili bilo sta slicno. Medjutim ako uzmes merge ili heap sort, potrebna ti je memorija za josh citavu strukturu (ovo u heap sortu moze da se izbegne, ako ne pravis privremenu strukturu, nego podatke odmah trpas u heap). Najnesigurniji si sa quick sortom, obzirom da se on skoro uvek realizuje rekurzivno, pa ne znas kada ce stek da popusti. Sve, u svemu heap sort mi se cini, kao fin izbor, a moras priznati da je malo nezgodno ubacivati npr. quick sort unutar heap-a (zbog drugacije konstrukcije memorijske strukture). Moja topla preporuka ti je da jedino na osnovu duzine ulaznog niza i eventualno rasporeda brojeva u njemu biras nacin sort-a, a umetanje jednog algoritma u drugi je obicno neisplativo. Jedna od onih "fora" koju si, nadam se, uzeo u obzir, je kad imas veliki niz sastavljen od celih brojeva (konacno velikih, npr ne veceg raspona od 100000). Tada mozes napraviti pomocni niz velicine opsega brojeva (onih pomenutih 100000) i jednim prolaskom O(n) popamtiti samo broj pojavljivanja svakog clana (to pamtis u nizu jer ti svakom clanu odgovara jedan indeks). Tada u sustini vec znas kako izgleda sortiran niz, jer imas clanove poredjane po velicini i njihovom broju pojavljivanja.

Na kraju, preporucujem ti da pogledas knjigu Introduction to Algorithms u izdanju MIT-a (knjiga ima 3 autora i podeblja je) iz koje mozes pogledati analizu najboljeg i najgoreg slucaja vecine algoritama, koja ti je potrebna.

Ukoliko je taj projekat za mlade talente, nekako vezan sa republickim centrom za talente (ono sto se odrzava u Kladovu), onda nemoj preterano da se zamaras jer je to najgore moguce takmicenje ikad izmisljeno (ja sam svojevremeno isao i umro sam od smeha...). Totalno su neozbiljni ljudi, a i nema nikakve konkurencije :))

Pozdrav i nadam se da vas nisam mnogo smorio...

Evo programa sa zakasnjenjem (danas sam se registrovao):

program testerasto;
const k=20;
type niz=array [1..k] of real;
var n,i: integer; o: real; x: niz;
procedure citaj;
procedure pisi;
procedure razmeni;(ovo su tri osnovne procedure, pa ih necu pisati);
begin
writeln('n:'); readln(n);
writeln('Unesite elemente:'); citaj(n,x);
o:=-1;
for i:=1 to n-1 do
begin
o:=-o;
if o*(x-x[i+1])>0 then razmeni(x,x[i+1]);
end;
pisi(n,x);
end.