Samenvatting eco

Let op!: The Θ(n2) bound on the worst-case running time, however, does not imply a Θ(n2) bound on the running time of insertion sort on every input!

Snelheid Vergelijking
Insertion sort Worst-case running time: Θ(n2)
Stabiel en in place
Running time: Ω(n) en O(n2)

Merge sort Worst-case running-time: Θ(n lg n) Stabiel en niet in place

Asymptotisch optimaal, want kost n log n tijd en ook tenminste n log n tijd.
Het opsplitsen: Θ(lg n)
Merge (de methode) : Θ(n)

Best: Ω(n log n)

Bucket sort Best en average: n Stabiel en niet in place
Worst-case: O(n2)
Bubble sort Worst-case running time: Θ(n2) Stabiel en in place
Best: Ω(n)

Selection sort Best: Ω(n^2) Worst: O(n^2) Niet stabiel en in place


Counting sort Worst-case running time: Θ(n + k) Stabiel en niet in place


Quick sort Worst-case running time: Θ(n2) Niet stabiel en in place
Best: Ω(n log n)

Heap sort Worst-case running time: Θ(n log n) Asymptotisch optimaal, want kost n log n tijd en ook tenminste n log n tijd.
Best: Ω(n log n)
Stabiel en in place

Radix sort Best, worst & average: n * k Stabiel en niet in place