Jesper Stocholm <jespers@stocholm.invalid> writes:
> Nu er det lidt tid siden jeg sidst sad med en akademisk indgang til
> sorteringsalgoritmer, men så vidt jeg kan huske er performance ved (alle)
> sorteringsalgoritmer meget afhængig af de data der skal sorteres.
Det er forskelligt. Nogle er afhængige, andre er ikke.
> Derfor kan BubbleSort meget vel outperforme QuickSort i dit
> tilfælde.
BubbleSort er kun hurtig på næsten-sorterede lister, og generelt
langsom (worst case: kvadratisk i antallet af elementer,
gennemsnitligt ca. det samme).
QuickSort er ofte hurtig. Dens worst case er også kvadratisk, men det
sker sjældent, og gennemsnitligt er den proportionalt med N*log(N)
(hvor N er antallet af elementer i listen). Den er nem at lave, har
lavt overhead og kræver ikke ekstra plads, så det er ofte den der
sorteringsalgoritme der bruges i biblioteker (som fx C's qsort)
MergeSort tager altid tid der er proportional med N*log(N), men kræver
ekstra plads at arbejde på (Bubble- og QuickSort kan gøres direkte i
den liste man arbejder på).
(Tiden måles her blot i hvor mange sammenligninger man laver på
elementerne i listen)
Hvis man har RIGTIGT mange elementer i listen, så skal man til at
tænke over hukommelsesstyring også, hvis man vil undgå at swappe
i evigheder. Google har tænkt meget over deres sortering :)
> > Det jeg mente var, at det nok ville
> > være hurtigst at sortere i databasen fremfor i asp-script.
>
> Det tror jeg til gengæld du har ret i.
Sandsynligvis. Hvis det havde været ASP.NET, som er compilet, så tror
jeg ikke forskellen nødvendigvis ville blive så stor (hvis du laver en
god implementation af en effektiv sorteringsalgoritme).
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
Art D'HTML: <URL:
http://www.infimum.dk/HTML/randomArtSplit.html>
'Faith without judgement merely degrades the spirit divine.'