Play and learn 300 000+ tabs online

Wednesday, August 11, 2010

Comparison of sorting algorithm

Sort Average Best Worst Space Stability Remarks
Bubble sort O(n^2) O(n^2) O(n^2) Constant Stable Always use a modified bubble sort
Modified Bubble sort O(n^2) O(n) O(n^2) Constant Stable Stops after reaching a sorted array
Selection Sort O(n^2) O(n^2) O(n^2) Constant Stable Even a perfectly sorted input requires scanning the entire array
Insertion Sort O(n^2) O(n) O(n^2) Constant Stable In the best case (already sorted), every insert requires constant time
Heap Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Constant Instable By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Depends Stable On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort O(n*log(n)) O(n*log(n)) O(n^2) Constant Stable Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.