note · algorithms
Overview
Overview
| Algorithm | Best Time Complexity | Worst Time Complexity | Average Time Complexity | Space Complexity | Stable? |
|---|---|---|---|---|---|
| Selection Sort | Ω(n^2) | θ(n^2) | O(n^2) | O(1) | N |
| Bubble Sort | Ω(n) | θ(n^2) | O(n^2) | O(1) | Y |
| Insertion Sort | Ω(n) | θ(n^2) | O(n^2) | O(1) | Y |
| Heap Sort | Ω(n log(n)) | θ(n log(n)) | O(n log(n)) | O(1) | N |
| Quick Sort | Ω(n log(n)) | θ(n log(n)) | O(n^2) | O(log(n)) | N |
| Merge Sort | Ω(n log(n)) | θ(n log(n)) | O(n log(n)) | O(n) | Y |
| Bucket Sort | Ω(n +k) | θ(n +k) | O(n^2) | O(n) | Y |
| Radix Sort | Ω(nk) | θ(nk) | O(nk) | O(n + k) | N |
| Count Sort | Ω(n +k) | θ(n +k) | O(n +k) | O(k) | Y |
| Shell Sort | Ω(n) | θ(n log(n)) | O(n log(n)) | O(1) | N |
| Tim Sort | Ω(n) | θ((n log(n))^2) | O((n log n (n))^2) | O(n) | Y |
| Tree Sort | Ω(n log(n)) | θ(n log(n)) | O(n^2) | O(n) | Y |
| Cube Sort | Ω(n) | θ(n log(n)) | O(n log(n)) | O(n) | Y |
Back toAll notes