[es] - Sortiranje VELIKOG niza

Ilija Studen
Novi Sad

Član broj: 3864
Poruke: 859
*.beotel.net

Sajt: www.activecollab.com

+1 Profil

^{10.08.2002. u 11:28 - pre 271 meseci}

U srednjoj sam koristio onaj lepi seljacki nacin da sortiram niz (tri promenljive, dva ciklusa, jedna promenljiva sluzi da se ne izgubi vrednost pri promeni mesta...), ali sam ga zaboravio... Moze li mi neko reci kako glasi?

Uz to, mozda nastane problem jer predvidjam da ce morati da radi sa bar 10000 clanova (ako ne i vise).

PS: Treba da sortira listu pomocu funkcije CompareText.

Pozdrav.

http://www.activecollab.com - Alat za upravljanje projektima

Odgovor na temu

BriganT
Tomislav Mihajlovic
Pa<->Bg/Srbija

Član broj: 4474
Poruke: 20
*.panet.co.yu

Sajt: www.dusan-prodekan.com

Profil

Re: Sortiranje VELIKOG niza

^{10.08.2002. u 14:31 - pre 271 meseci}

ovo ti je sortiranje, a ti sam ubaci CompareText!
...
for i:=2 to n do
if a>a[i-1] then
else begin
b:=a[i-1];
a[i-1]:=a;
a:=b;
end;
...
Sad zavisi da li hoces rastuci ili opadajuci.

Nadam se da je dobro, sad sam ga smislio!
Brigants Lion

Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.telekom.yu

+1 Profil

Re: Sortiranje VELIKOG niza

^{10.08.2002. u 19:05 - pre 271 meseci}

Cini mi se kao da mislis na bubblesort, mada ti je sigurno bolje da koristis neki brzi algoritam tipa quicksort ili shellsort...

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost

+5 Profil

Re: Sortiranje VELIKOG niza

^{10.08.2002. u 23:33 - pre 271 meseci}

ma bre zasto ljudi prave sve brze i brze kompjutere?

da bi mi i dalje pisali programe u asembleru (tako je najbrze) i trosili sate da optimizujemo algoritam koji ce da bude 0.5 sec. brzi od neoptimizovanog.

ma dajte bre ljudi. jer znate vi sta je to 10,000 clanova niza i jedan obican bouble sort! ma to ce da radi oko sekunde na bilo kom savremenom comp-u (pII/500Mhz)

ne kazem ja da treba uvek ovako raditi, ali je najcesce isplativije! treba znati i quick sort, i sta je to/kako se koristi hash-ovanje itd... ali ako treba jedared da uredish taj niz, batali i trosi sive celije na nesto teze.

sa druge strane, ako taj sort treba da se dogadja vise desetina puta u sekundi zbog nekog razloga, predlazem jedan od sledecih koraka:
1) napisi kao bouble sort
2) proveri sam razlog zasto uopste treba da se sortira 10-ak puta u sekundi. tu je verovatno greska u projektovanju

eh da, umalo da zaboravim... ono gore je lose... evo ga obican bouble sort...
(tackice da bi se kod lepo video)

Code:

for i:=1 to n-1 do
....for j:=i+1 to n do
........if CompareText(a[[b][/b]i], a[j])>0 then begin
............p:=a[i[b][/b]];
............a[i[b][/b]]:=a[j];
............a[j]:=p;
........end;

napomena: ovo je u rastucem poretku, od a do z (valjda ;), ako oces u opadajucem, promeni uslov u <0

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

Chimera144
Beograd

Član broj: 4758
Poruke: 12
*.beg.sezampro.yu

Profil

Re: Sortiranje VELIKOG niza

^{11.08.2002. u 09:41 - pre 271 meseci}

Ako mu je strvarno potrebno nesto brze evo QuickSorta:

Code:

procedure QuickSort (levo,desno: integer; var a:niz);
var
...x,i,k: integer;
begin
...if levo<desno
...then begin
............x:=a[levo]; k:=levo;
..............for i:=levo+1 to desno do
...............if a[i]<=x
...............then begin
........................k:=k+1;
........................razmeni(a[k],a[i]);
......................end;
............razmeni(a[levo],a[k]);
............QuickSort(levo,k-1,a);
............QuickSort(k+1,desno,a);
.........end;
end;

P.S. Ako neko zeli moze da napise ShellSort jer me bas zanima kako izgleda.

[Ovu poruku je menjao Chimera144 dana 11.08.2002 u 12:08 PM GMT]

[Ovu poruku je menjao Chimera144 dana 11.08.2002 u 12:10 PM GMT]

Odgovor na temu

broker

Član broj: 2415
Poruke: 8514
*.ptt.yu

+11 Profil

Re: Sortiranje VELIKOG niza

^{11.08.2002. u 11:18 - pre 271 meseci}

Ako se radi o sortiranju stringova ima to vec odradjeno u Dlphiju u TStrings (TStringList) klasi i to koliko se secam QuickSort-om.

Odgovor na temu

Ilija Studen
Novi Sad

Član broj: 3864
Poruke: 859
*.beotel.net

Sajt: www.activecollab.com

+1 Profil

Re: Sortiranje VELIKOG niza

^{11.08.2002. u 12:16 - pre 271 meseci}

Da vas malo upornam sa celim problemom... Koristim komponentu klase TLMDListBox. Dakle, nije standardna lista vec ima dve kolone sa Headerima. Koristi paradox tabelu za koju je predvidjeno da nema Unoque polja sem ID (AutoInc). U prvu kolonu smestam ID a u drugu string iz tabele. Ako budem koristio QuickSort sortirace po kompletnom stringu (LMDListBox razdvaja kolone pomocu Delimitera ';'), dakle

1;NekiString
2;NekiDrugiString
...
n;n-tiString

Mislim da vidite u cemu je problem... LMDListBox ima i jednu zanimljivu proceduru SpecialSort. Kao parametar joj se daje Int niz i ona na osnovu njega sortira. Probacu nesto da izvedem pomocu nje... A vama ako padne nesto na pamet, ne stedite tastaturu.

PS. Ja nemam obicaj da postavljem lake probleme.

http://www.activecollab.com - Alat za upravljanje projektima

Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.telekom.yu

+1 Profil

Re: Sortiranje VELIKOG niza

^{11.08.2002. u 13:31 - pre 271 meseci}

Citat:

Chimera144:

P.S. Ako neko zeli moze da napise ShellSort jer me bas zanima kako izgleda.

Algoritam je napisan u MODULA-2 programskom jeziku, ali zbog njegove velike slicnosti
sa paskalom se nadam da cete bez problema moci da ga procitate...

Code:

PROCEDURE ShellSort(VAR a: niz);
CONST faktor = 2.55;
VAR i, j, granicai, prvi, korak : CARDINAL;
....temp : element; (* element niza, slog koji u sebi sadrzi polje kljuc na osnovu kog se elementi sortiraju *)
....rkraj, wnastavi : BOOLEAN;

BEGIN
....korak := maxniz; (* maxniz je konstanta koja oznacava maksimalnu velicinu niza kog sortiramo *)
....REPEAT
........korak := TRUNC(FLOAT(korak) / faktor); (* u svakom krugu petlje korak se smanjuje, dok ne dodje do 1 *)
........IF korak < 1 THEN
............korak := 1
........END;
........prvi := korak + 1;
........granicai := maxniz - korak;
........REPEAT
................DEC(prvi);
................i := prvi + korak;
................wnastavi := i <= maxniz;
................WHILE wnastavi DO
(* deo koji sledi je modifikovana verzija sortiranja umetanjem *)
........................IF a[i].kljuc < a[i-korak].kljuc THEN (* ovo je ono gore spomenuto polje kljuc *)
................................temp := a[i];
................................j := i;
................................REPEAT
........................................j := j - korak;
........................................a[j+korak] := a[j];
........................................IF j <= korak THEN
................................................rkraj := TRUE
........................................ELSE
................................................rkraj := a[j-korak].kljuc <= temp.kljuc
........................................END
................................UNTIL rkraj;
................................a[j] := temp;
........................END;
........................IF i <= granicai THEN
................................i := i + korak
........................ELSE
................................wnastavi := FALSE
........................END
................END
........UNTIL prvi = 1
....UNTIL kraj = 1
END ShellSort;

Osnovna ideja Shell-ovog sortiranja je da se niz podeli na podnizove tipa
(1, 1 + korak, 1 + 2*korak,.....)
(2, 2 + korak, 2 + 2*korak,.....)
......
(korak, korak + korak, korak + 2*korak,.....)

a svaki od ovih podnizova da se sortira umetanjem (niz se podeli na sortirani i nesortirani deo. uzima se prvi element
nesortiranog dela i 'umetne' se na odgovarajuce mesto u sortiranom delu)

Preuzeto iz knjige "Strukture podataka i algoritmi" Dr. Djura Paunic, Univerzitet u Novom Sadu, Prirodno-matematicki
Fakultet Novi Sad, 1997.

[Ovu poruku je menjao mucky dana 11.08.2002 u 05:13 PM GMT]

Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.telekom.yu

+1 Profil

Re: Sortiranje VELIKOG niza

^{11.08.2002. u 13:47 - pre 271 meseci}

Citat:

zombie / DDG:
ne kazem ja da treba uvek ovako raditi, ali je najcesce isplativije! treba znati i quick sort, i sta je to/kako se koristi hash-ovanje itd... ali ako treba jedared da uredish taj niz, batali i trosi sive celije na nesto teze.

kada bi svih 100 programera neke virtuelne firme olako bacali tih trichavih 0.5-1 sec , sta mislis koliko bi program sekundi bio sporiji od konkurentskog? I tu ti ne vredi jaka masina, jer je konkurentski brzi i na jacoj masini :)))

sortiranje nizova, osnovne vrste struktura podataka (ukljucujuci i hash tabele) je nesto sto svaki programer jednostavno mora da zna... to ti je nesto kao azbuka programiranja...

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost

+5 Profil

Re: Sortiranje VELIKOG niza

^{12.08.2002. u 01:03 - pre 271 meseci}

ali ako tih 100 programera izgubi tih 2-3 sata na 100tinak takvih usteda od 0.5sec, onda ce taj program kasniti sa izlaskom na trziste nekih 100tinak nedelja sto je u nasoj industriji kao 100 godina...

i ja sam nekad tako radio, ali je nasa industrija toliko nemilosrdna, da se uvek mora gledati ekonomski efekat svega. tj. sta je ekonomicnije... verovao sam ja u 'umetnost programiranja', (i dalje verujem) i u nalazenje najoptimalnijeg i najlepseg algoritma za dati problem, ali od kada se profesionalno bavim ovim poslom, uvek 2 puta razmislim pre nego sto pocnem da programiram.

i da napomenem da se kod nas software uglavnom radi "za juce", tj da su rokovi takvi, da ne dozvoljavaju lepo programiranje. u zemlji u kojoj se za hardware i dalje vise izdvaja nego za software (nekoliko puta), ja se cesto opredeljujem da taj isti hardware i radi veci deo posla, jer je vise placen. ;)

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu