| Straight Selection Sort | Quick Sort | |
|---|---|---|
| Speicheraufwand | O(n) | O(n), aber mehr als bei Straight Selection |
| Zeitaufwand | O(n2) | best case: O(n × log2 n) worst case: O(n2) |
Ist n (n < 20) klein, so wirkt sich der Vorteil von Quicksort aber nicht aus, da pro Durchlauf die einzelnen Anweisungen deutlich zeitintensiver sind.
| n | O(n2) | O(n × log2 n) |
|---|---|---|
| 5 | 25 | 12 |
| 10 | 100 | 34 |
| 20 | 400 | 87 |
| 50 | 2.500 | 283 |
| 100 | 10.000 | 665 |
| 1.000 | 106 | 9.966 |
| 10.000 | 108 | 13.288 |
| 1.000.000 | 1012 | ca. 2 × 107 |
© Ralph-Erich Hildebrandt, 12. Dezember 2004