Rekursion
- slide 26 : 27
Quicksort (4)
En god implementation plejer at være blandt de allerbedste sorteringsmetoder - men der er ingen garanti
Køretid i bedste tilfælde:
I størrelsesordenen
n
·
log
2
(n)
sammenligninger og ombytninger.
Køretid i værste tilfælde
I størrelsesordenen
n
2
sammenligninger og ombytninger.
n
n
2
n
·
log
2
(n)
100
10.000
664
1000
1.000.000
9.966
10.000
100.000.000
132.887
100.000
10.000.000.000
1.660.964
Det kan vises at en sortering med i størrelsesordenen
n
·
log (n)
sammenligninger og ombytninger er optimal.
