[es] - Sortiranje niza

anon676

Član broj: 676
Poruke: 759
*.verat.net

Profil

^{04.05.2002. u 13:26 - pre 267 meseci}

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]:

Code:

DO WHILE (ey < maksimumx) AND NOT fsort
ey = ey + 1
    FOR i = 0 TO maksimumx - ey - 1
        fsort = 1

                IF redx!(i) > redx!(i + 1) THEN
                        SWAP redx!(i), redx!(i + 1)
                        fsort = 0
                END IF
        NEXT i

LOOP

eh sad funkcija swap, ti zamenjuje sledece:

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

Code:

    int promenljiva1 = 5, promenljiva2 = 6,temp;

    temp = promenljiva2;
    promenljiva2 = promenljiva1;
    promenljiva1 = temp;

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

Code:

    int promenljiva1 = 5, promenljiva2 = 6, temp;
    int *pn;

    pn = &promenljiva1;
    temp = *pn;
    *pn = promenljiva2;
    promenljiva2 = temp;

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.

Odgovor na temu

kajla
Milorad Janković
Beograd

Član broj: 445
Poruke: 909
195.252.103.*

+2 Profil

Re: Sortiranje niza

^{05.05.2002. u 02:25 - pre 267 meseci}

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

poz.

Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.165.EUnet.yu

+3 Profil

Re: Sortiranje niza

^{05.05.2002. u 02:51 - pre 267 meseci}

Citat:

kajla:
Treba da sortiram niz (bez korišćenja pomoćnog niza) tako da bude zadovoljeno:
a[1]>=a[2]<=a[3]>=a[4]<=a[5]>=...

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;

Odgovor na temu

anon676

Član broj: 676
Poruke: 759
*.verat.net

Profil

Re: Sortiranje niza

^{05.05.2002. u 13:02 - pre 267 meseci}

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

Odgovor na temu

kajla
Milorad Janković
Beograd

Član broj: 445
Poruke: 909
*.absolutok.com

+2 Profil

Re: Sortiranje niza

^{06.05.2002. u 13:30 - pre 267 meseci}

Citat:

srki:
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;

Evo programa:

Code:

program sortiranje (input, output);
const max=50;
type niz=array [1..max] of integer;
var a:niz;
    n,i,j:integer;
procedure zameni (var a:niz;i,j:integer);
var pom:integer;
begin
     pom:=a[i];a[i]:=a[j];a[j]:=pom
end;
function max_i (a:niz;i:integer):integer;
var max,j:integer;
begin
     max:=i;
     for j:=i to n do
         if a[j]>a[max] then max:=j;
     max_i:=max
end;
function min_i (a:niz;i:integer):integer;
var min,j:integer;
begin
     min:=i;
     for j:=i to n do
         if a[j]<a[min] then min:=j;
     min_i:=min
end;
begin
     write('Unesite n: ');readln(n);
     for i:=1 to n do
     begin
          write('Unesite broj: ');
          readln(a[i])
     end;
     for i:=1 to n do
     begin
          if odd(i) then
              zameni(a,i,max_i(a,i))
          else
              zameni(a,i,min_i(a,i))
     end;
     for i:=1 to n do writeln(a[i])
end.

poz.

Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu

Profil

Re: Sortiranje niza

^{10.06.2002. u 04:56 - pre 266 meseci}

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.

Odgovor na temu

BlueIce
Marko Marić
Novi Sad

Član broj: 4448
Poruke: 215
*.165.EUnet.yu

Profil

Re: Sortiranje niza

^{27.06.2002. u 09:31 - pre 265 meseci}

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

Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu

Profil

Re: Sortiranje niza

^{27.06.2002. u 12:56 - pre 265 meseci}

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...

Odgovor na temu

[C]ompiler

Član broj: 4482
Poruke: 31
*.verat.net

Profil

Re: Sortiranje niza

^{29.06.2002. u 15:45 - pre 265 meseci}

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.

Odgovor na temu