| Algorithm | Worst Case | Average Case | Best Case | Min. no. of swaps | Max. no. of swaps |
|---|---|---|---|---|---|
| Bubble | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ |
| Selection | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ | 0 (when array is already sorted) | $\theta(n^{2})$ |
| Insertion | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n)$ (when array is sorted) | 0 (when array is already sorted) | $\theta(n^{2})$ |
| Quick | $\theta(n^{2})$ (when array is sorted, and pivot taken from one end) | $\theta(n\lg n)$ | $\theta(n\lg n)$ | 0 (when array is already sorted) | $\theta(n^{2})$ |
| Merge | $\theta(n\lg n)$ | $\theta(n\lg n)$ | $\theta(n\lg n)$ | Is not in-place sorting | Is not in-place sorting |
| Heap | $\theta(n\lg n)$ | $\theta(n\lg n)$ | $\theta(n\lg n)$ | $O(n\lg n)$ | $\theta(n\lg n)$ |
| Algorithm | Worst Case | Average Case | Best Case | Min. no. of swaps | Max. no. of swaps |
|---|---|---|---|---|---|
| Bubble | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ |
| Selection | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n^{2})$ | 0 (when array is already sorted) | $\theta(n^{2})$ |
| Insertion | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n)$ (when array is sorted) | 0 (when array is already sorted) | $\theta(n^{2})$ |
| Quick | $\theta(n^{2})$ (when array is sorted, and pivot taken from one end) | $\theta(n\lg n)$ | $\theta(n\lg n)$ | 0 (when array is already sorted) | $\theta(n^{2})$ |
| Merge | $\theta(n\lg n)$ | $\theta(n\lg n)$ | $\theta(n\lg n)$ | Is not in-place sorting | Is not in-place sorting |
| Heap | $\theta(n\lg n)$ | $\theta(n\lg n)$ | $\theta(n\lg n)$ | $O(n\lg n)$ | $\theta(n\lg n)$ |
GATECSE