Ole Laursen <[EMAIL PROTECTED]> writes:
> > M�ske kunne vi bruge tr�sorteringen som et eksempel p�, hvordan
> > man kunne lave det, hvis det drejer sig om at kunne finde sine
> > data hurtigt igen.
>
> Mja, jeg ville nu foretr�kke quicksort, ogs� fordi den jo er
> s�rdeles kendt - det er den man faktisk (i lettere modificeret
> udgave) bruger.
Ja, man kan bruge Quicksort til at sortere sine data med, men hvis man
s� gemmer dem i en k�det liste, er man jo egentlig lige vidt: man skal
stadig igennem n/2 elementer f�r man finder det rigtige. Det g�lder jo
lige meget hvilken algoritme man brugte dengang da man sorterede.
> > Apropos pointere: kan du f� gdb til at vise indholdet af et
> > element? Hvis jeg pr�ver med 'print Element->Naeste' brokker den
> > sig over at der ikke er noget 'medlem' der hedder 'naeste',
> > 'Naeste' eller hvad jeg nu pr�ver med.
>
> Tja, det er lang tid siden jeg sidst har pr�vet at bruge gdb, og
> dengang var det kun overfladisk. Jeg plejer at klare mig med at
> udskrive henvisningsv�rdierne undervejs ved at tilf�je sm� kald i
> koden.
Ah - det lyder som en noget bedre l�sning :-)
> I anledning af at det lykkedes mig at blive f�rdig med den sidste
> fysikrapport i l�bet af blot 5/2 timer, har jeg kigget lidt p� din
> kode. Jeg m� tilst� at jeg ikke umiddelbart forst�r den helt - det
> ser ud til at du fors�ger at flytte elementerne om bag pivoten i den
> samme liste hver gang et element er st�rre? Er det af
> optimeringshensyn?
>
> I s� fald vil jeg lige benytte lejligheden til at tr�kke et citat af
> Don Knuth ud af �rmet, "premature optimization is the root of all
> evil" (idet det godt nok ikke helt er t�nkt brugt i denne
> sammenh�ng, men det beh�ver I jo ikke at vide ;-).
>
> Jeg tror det smarteste er at skrive algoritmen om til noget i denne
> retning:
>
> pivotsortering:
> st�rre = nil
> lavere = nil
> pivot = find_pivot
>
> l�b alle elementerne igennem
> hvis st�rre end pivots n�gle
> anbring i st�rre { husk at tilfoej_element kan bruges }
> ellers
> anbring i lavere
>
> kald pivotsortering med st�rre
> kald pivotsortering med lavere
>
> return�r liste sammensat af lavere, pivot og st�rre
>
> hvor
>
> find_pivot:
> return�r f�rste element
>
> i f�rste omgang. Trinet med at sammens�tte den endelige liste ud af
> pivotelementet og de to andre lister b�r nok udarbejdes i en s�rskilt
> rutine af overskuelighedshensyn (en rutine b�r kun g�re ca. en ting).
Det var s�dan set ogs� det jeg startede med at lave. Men s� var der jo
det problem, at jeg enten bliver n�dt til at allokere nye hukommelse
til *st�rre* og *lavere* (hvilket tager tid og spilder hukommelse)
eller ogs� skal jeg bytte rundt i selve listen. Det var det jeg
pr�vede p�, men s� gik der kludder i alle mine pointere :-(
> Er dette ikke lettere at g� til? N�r dette virker, kan vi s� senere
> optimere p� det - det kunne jo faktisk v�re smukt at give et rids
> over forfinelsen fra dette f�rste udkast til den endelige version
> (m�ske bliver det for langt med kode i rapporten, men s� m�ske med
> pseudokode).
>
> Jeg evt. skrive koden til denne udgave, det er ikke noget problem,
> men jeg t�nkte at det ville fjerne det sjove ved. Men skal jeg
> alligevel?
Tja - jeg vil da gerne g�re et fors�g til. Vi kan jo alligevel ikke
aflevere noget f�r hele rapporten er f�rdig...
--
Best regards,
Martin Geisler
Checkout http://www.gimpster.com for:
PHP Weather => Shows the current weather on your webpages.
PHP Shell => A telnet-connection (almost :-) in a PHP page.
