[ Ilija Studen @ 10.08.2002. 11:28 ] @
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.
[ BriganT @ 10.08.2002. 14:31 ] @
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!
[ mucky @ 10.08.2002. 19:05 ] @
Cini mi se kao da mislis na bubblesort, mada ti je sigurno bolje da koristis neki brzi algoritam tipa quicksort ili shellsort...
[ -zombie- @ 10.08.2002. 23:33 ] @
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
[ Chimera144 @ 11.08.2002. 09:41 ] @
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]
[ broker @ 11.08.2002. 11:18 ] @
Ako se radi o sortiranju stringova ima to vec odradjeno u Dlphiju u TStrings (TStringList) klasi i to koliko se secam QuickSort-om.
[ Ilija Studen @ 11.08.2002. 12:16 ] @
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.
[ mucky @ 11.08.2002. 13:31 ] @
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]
[ mucky @ 11.08.2002. 13:47 ] @
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...
[ -zombie- @ 12.08.2002. 01:03 ] @
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. ;)
[ mucky @ 12.08.2002. 02:13 ] @
Svestan sam ja da je kod nas to tako... Cak stavise, ljudi ZELE da programi rade sporo da bi sto manje uradili za sto vise vremena :)) Ali i dalje smatram da neke osnovne stvari kao sto je sortiranje nizova treba znati i razumeti, a ne lupiti babl-sort pa kud koji mili moji.