Hej allesammen!
Nu da vi ved, at vi ikke skal op i datalogi (Kristian og jeg skal i
hvert fald ikke), s� bliver vores projekt nok lagt lidt p� is...
Det er �rgeligt, at vi ikke skal op i datalogi, i stedet for s�dan
noget som dansk eller historie. Jeg sad faktisk lige og legede lidt
med programmet i morges.
Jeg testede hvor lang tid de to algoritmer var om at sortere lister af
forskellig l�ngde. Det viste sig, at tidsforbruget for Oles algoritme
steg nogenlunde line�rt, mens det sted en anelse eksponentielt for min
algoritme. Jeg brugte den danske ordliste, s� jeg kunne teste helt op
til 350000 elementer.
graf.png
program hovedprogram;
uses
liste,
bobbelsortering,
indsaetningssortering,
traesortering,
pivotsortering,
sammensaetningssortering,
gnutidstagning;
{ indl�ser linjerne i en tekstfil og stopper dem ind i
den k�dede liste}
procedure indlaes_data(var liste : henv;
filnavn : string);
var
fil : text;
s : noegle_type;
begin
assign(fil, filnavn);
reset(fil);
repeat
readln(fil, s);
tilfoej_element(liste, s);
until eof(fil);
close(fil);
end;
procedure udskriv_resultat(metodenavn : string;
tid : integer);
begin
writeln(' ', metodenavn,
' brugte ', tid:4, ' ms');
end;
{ k�rer en test af sorteringsrutinerne givet en liste
(i omvendt orden) }
procedure udfoer_test(dataliste : henv; antal_elementer : integer);
var
bobbelliste, indsaetningliste, sammensaetningliste,
pivotliste, traeliste : henv;
trae : trae_henv;
starttid : integer;
begin
{
bobbelliste := listekopi(dataliste, antal_elementer);
starttid := tiden;
bobbelsortering(bobbelliste);
udskriv_resultat('Boblesortering ',
tiden - starttid);
slet_liste(bobbelliste);
indsaetningliste := listekopi(dataliste, antal_elementer);
starttid := tiden;
indsaetningssortering(indsaetningliste);
udskriv_resultat('Inds�tningssortering ',
tiden - starttid);
slet_liste(indsaetningliste);
}
sammensaetningliste := listekopi(dataliste, antal_elementer);
starttid := tiden;
sammensaetningssortering(sammensaetningliste);
udskriv_resultat('Sammens�tningssortering',
tiden - starttid);
slet_liste(sammensaetningliste);
pivotliste := listekopi(dataliste, antal_elementer);
starttid := tiden;
pivotsortering(pivotliste);
udskriv_resultat('Pivotsortering ',
tiden - starttid);
slet_liste(pivotliste);
{
traeliste := listekopi(dataliste, antal_elementer);
starttid := tiden;
trae := traesortering(traeliste);
udskriv_resultat('Tr�sortering ',
tiden - starttid);
slet_liste(traeliste);
slet_trae(trae);
}
end;
procedure test;
var
l: henv;
begin
l := nil;
indlaes_data(l, 'eksempel.txt');
l := listekopi(l, -1);
sammensaetningssortering(l);
end;
var
dataliste : henv;
i : integer;
begin
i := 0;
writeln;
writeln('Tester en liste hvor 1000% af elementerne er ombyttet.');
indlaes_data(dataliste, '1000-liste.txt');
while i < 350000 do
begin
i := i + 5000;
writeln(i:7, ' elementer:');
udfoer_test(dataliste, i);
end;
slet_liste(dataliste);
{
writeln;
writeln('Tester en liste hvor 100% ',
'af elementerne er ombyttet:');
indlaes_data(dataliste, '100-liste.txt');
udfoer_test(dataliste);
slet_liste(dataliste);
writeln;
writeln('Tester en liste hvor 50% ',
'af elementerne er ombyttet:');
indlaes_data(dataliste, '50-liste.txt');
udfoer_test(dataliste);
slet_liste(dataliste);
writeln;
writeln('Tester en liste hvor 20% ',
'af elementerne er ombyttet:');
indlaes_data(dataliste, '20-liste.txt');
udfoer_test(dataliste);
slet_liste(dataliste);
writeln;
writeln('Tester en liste hvor 5% ',
'af elementerne er ombyttet:');
indlaes_data(dataliste, '5-liste.txt');
udfoer_test(dataliste);
slet_liste(dataliste);
}
end.
unit liste;
interface
type
noegle_type = string[50];
henv = ^element;
element = record { indeholder et listeelement }
naeste : henv;
noegle : noegle_type;
end;
{ inds�tter et nyt element i starten af listen med en given n�gle }
procedure tilfoej_element(var liste: henv; noegle: string);
{ returnerer en kopi (i omvendt r�kkef�lge) af en liste }
function listekopi(liste : henv; antal_elementer : integer): henv;
{ udskriver n�glerne i en liste }
procedure udskriv_liste(liste: henv);
{ sletter alle elementerne i en liste }
procedure slet_liste(var liste: henv);
implementation
procedure tilfoej_element(var liste: henv; noegle: string);
var
element: henv;
begin
new(element);
element^.noegle := noegle;
element^.naeste := liste; { lad elementet henvise til hvad h henviste til}
liste := element; { lad h henvise til elementet }
end;
{ RETMIG: sandsynligvis overfl�dig }
procedure slet_element(var liste: henv; noegle: string);
var
h, forrige: henv;
begin
h := liste;
forrige := nil;
while (h <> nil) and (h^.noegle <> noegle) do
begin
forrige := h;
h := h^.naeste;
end;
if h <> nil then
begin
if forrige = nil then
liste := h^.naeste
else
forrige^.naeste := h^.naeste;
dispose(h);
end;
end;
procedure slet_liste(var liste: henv);
var
h, naeste: henv;
begin
h := liste;
{ l�b igennem alle elementerne }
while h <> nil do
begin
{ husk hvad den n�ste henviser til og slet den nuv�rende }
naeste := h^.naeste;
dispose(h);
h := naeste;
end;
liste := nil; { mark�r at listen er tom }
end;
function listekopi(liste : henv; antal_elementer : integer): henv;
var
h : henv;
n : integer;
begraensning : boolean;
begin
n := 0;
h := liste;
result := nil;
{ hvis antal_elementer er mindre end 0, skal vi ikke lave nogen
begr�nsning }
if antal_elementer < 0 then
begin
antal_elementer := 1;
begraensning := false;
end
else
begraensning := true;
while (h <> nil) and (n < antal_elementer) do
begin
tilfoej_element(result, h^.noegle);
h := h^.naeste;
if begraensning then
inc(n);
end;
end;
procedure udskriv_liste(liste: henv);
var
h: henv;
begin
h := liste;
while h <> nil do
begin
write(h^.noegle, ' '); { udskriv n�gle }
h := h^.naeste;
end;
writeln;
end;
end.
--
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.
graf.png