Created 2005-09-23 Modified 2007-01-01
Chelton Evans
Sorting Algorithms
Intro
Sorting Methods Summary
Computational Geometry Algorithms
Warning
Most computer scientists grew up with the concept of average and worst case complexity. Actually there was a time when these ideas were mysterious and difficult to grasp - as I read one of the original papers of the time trying to convey to the reader the idea of O(n^k).
So again like a new thing the randomized algorithms input has woken us up to expected complexity. This is where the input is randomized and fed into the algorithm. Its power is that it turns algorithms that are potentially weak on a data set into their optimal complexity - with extremely high confidence. And I mean extreme confidence.
For all practical purposes the expected complexity is the worst case complexity.
There are those of you who may howl and carry on but the facts are in and any argument to the contrary is ill informed and emotive.
| Bubble sort with Randomized Input | O(n^2) |
| Insertion Sort | O(n^2) |
| Heap Sort | O(n log n ) |
| AVL Trees | O( n log n ) |
| Quick Sort with Randomized Input | O( n log n ) |
| Insertion into a binary tree with Randomized Input | O( n log n ) |
| Shell Sort | O(n^(3/2)) |
| Merge Sort | O( n log n ) |
| Bucket Sort with Insertion Sort in Lists | O(n) best, O(n^2) worst |
| Bucket Sort with O( n log n ) sort in lists | O(n) best, O( n log n ) worst |
The randomized input has as much influence on computational geometry. For example consider the quick hull algorithm which has average O( n log n ) and worst O(n^2). By randomizing its input it has O( n log n ) complexity. This happens to be the theoretical limit.
You may now call me a hypocrite, but there may still be data sets that bring back the worst case complexity. However the algorithms are much more robust and do not suffer in normal situations as the quick sort did on an already sorted data set.