Comparison sort
Name | Best Time | Average Time | Worst Time | Space | Stable | Method |
Selection sort | O(n2) | O(n2) | O(n2) | O(1) | No | Selection |
Insertion sort | O(n) | O(n2) | O(n2) | O(1) | Yes | Insertion |
Bubble sort | O(n) | O(n2) | O(n2) | O(1) | Yes | Exchanging |
Merge sort | O(nlogn) | O(nlogn) | O(nlogn) | Depends; worst case is n | Yes | Merging |
Heap sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | No | Selection |
Quick sort | O(nlogn) | O(nlogn) | O(n2) | O(logn) | Depends | Partitioning |
Non-comparison sort
Name | Best Time | Average Time | Worst Time | Space | Stable |
Counting sort | ---- | O(n+r) | O(n+r) | O(n+r) | Yes |
Radix sort | ---- | O(n*k/d) | O(n*k/d) | O(n) | Yes |
Bucket sort | ---- | O(n+r) | O(n+r) | O(n+r) | Yes |
Selection Sort:
Heap Sort:
Quick Sort:
No comments:
Post a Comment