> > Problemet med tr�sorteringen er bare at metoden bliver faktisk det
> > samme som sammens�tningssorteringen.
>
> Rent faktisk, s� laver en tr�sortering liges� mange sammenligninger
> som en Quicksort, i f�lge papirerne.
Yes, du har ret, jeg er kommet til at rode rundt i det. Tr�sortering
er n�sten quicksort, smartere hvis man skal bruge tr�et, ellers
usmartere.
> Men normalt sorterer man jo netop ogs� data for at kunne finde noget
> hurtigt igen. Der er jo fordelen ved et tr�: har man 1024 elementer
> (og tr�et er balanceret nogenlunde ordentligt) s� skal man kun lave
> h�jst 10 sammenligninger for at finde det, mens man skal lave cirka
> 512 sammenligninger med en k�ded liste.
Men problemet er at hvis vi begynder at se p� det p� den m�de, s�
falder de andre algoritmer ligesom til jorden. Hvor er
sammenligningsgrundlaget?
> Det er da smart, samtidig med at koden der skal til for at
> vedligeholde et bin�rt tr� er simpel.
Det sidste er jeg ikke helt enig med dig i. :-)
> > Har du det andet kode du fremstillede? Algoritmen er jo ikke s�
> > lang, det m� v�re muligt at finde fejlen.
>
> Problemet var, at jeg �ndrede p� listen da jeg skulle smide elementer
> over p� h�jre eller venstre side af min pivot. Koden er faktisk med i
> pakken - pivotsortering.pas.
Fint, jeg kigger lige p� det s� snart som muligt.
> Ordene bliver sorteret s�dan som man kunne forvente: efter tegnenes
> ASCII-v�rdier. Grunden til at jeg pr�vede med den danske liste, var
> for at se hvordan det virkede n�r vi havde *rigtig* mange ord.
Mm. Det tager vist ogs� en hulens tid at generere dem ud fra de r�
lister der bliver benyttet.
> > Klart nok - n�r de er sorterede, f�r du en n�sten almindelig k�de.
> > Det er derfor at hvis vi skulle have kigget p� tr�er, s� skulle vi
> > have kigget p� en smart (men ret indviklet) metode til at undg�
> > dette f�nomen.
>
> Det er ikke s� indviklet endda - koden fylder dog lidt mere (2 sider).
> Som du nok ved, s� drejer det sig om at man roterer visse dele af
> tr�et n�r man inds�tter og fjerner elementer. If�lge min bog, skal man
> cirka igang med at /balancere/ tr�et hver anden gang man inds�tter et
> element.
Det jeg t�nker p� er alts� indviklet - jeg kan ikke huske om jeg fik
kopieret det der st�r om AVL-tr�er som vist er den rigtige m�de at
ordne det hele p� (det var dem jeg t�nkte p�), men selvom koden dertil
ikke er s� lang, skal der en hulens masse forklaringer og diagrammer
til. Da jeg var f�rdig med at l�se afsnittet, var jeg ikke engang
overbevist om at det virkeligt virkede. :-)
> Jeg blander da ikke dansk og engelsk sammen. Jeg skriver koden p�
> engelsk, og t�nkte s� at jeg hellere m�tte skrive kommentarerne p�
> dansk, da I ellers sikkert ville g� helt amok.
Og det kalder du s� ikke at blande dansk og engelsk sammen? :-)
Selvom du ogs� oversatte kommentarerne, ville det jo heller ikke
hj�lpe fordi resten af programmet nu er skrevet p� dansk. N'ce est pas?
> Personligt har jeg det rigtig skidt med alle de ���'er der er blevet
> "escaped" til ae oe aa. Det ser i mine �jne mystisk ud n�r man har en
> funktion der hedder 'sammensaetningssortering' - ordene flyder sammen
> og indeholder 'tegn' der ikke findes i normal dansk (ae).
>
> M�ske vi skulle bruge nogle underscores (_) til at dele ordene med?
Jeps, det er jo det jeg har gjort. Men det hedder jo
sammens�tningssortering og ikke sammen s�tnings sortering.
> Eller ogs� kunne vi g�re ligesom i Delphi og mange andre steder: bruge
> store og sm� bogstaver til at adskille ordene.
Det er det som du har gjort, og som ikke rigtigt passer sammen med det
andet jeg har lavet.
Personligt bryder jeg mig ikke s� meget om at blande store og sm�
bogstaver (det er m�ske en del af Unix-opdragelsen), men vi kunne for
min skyld sagtens have lagt os fast p� det i stedet for _, bare vi
alle brugte det samme. Men nu har jeg jo allerede skrevet resten af
koden med _ og s� er det lidt som at g� to skridt frem og to tilbage
igen at �ndre det.
Vi skal jo heller ikke bruge koden mere end et par uger endnu til at
vise frem, kan vi s� ikke sige at det der er fastlagt nu er godt nok?
--
Ole Laursen
http://sunsite.dk/olau/
