Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 47: | Line 47: | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
+ | |$O(nlgn)$ | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
− | |||
|} | |} | ||
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(nlgn)$ | $\theta(nlgn)$ | 0 (when array is already sorted) | $\theta(n^{2})$ |
Merge | $\theta(nlgn)$ | $\theta(nlgn)$ | $\theta(nlgn)$ | Not in place sorting | Not in place sorting |
Heap | $\theta(nlgn)$ | $\theta(nlgn)$ | $\theta(nlgn)$ | $O(nlgn)$ | $\theta(nlgn)$ |
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(nlgn)$ | $\theta(nlgn)$ | 0 (when array is already sorted) | $\theta(n^{2})$ |
Merge | $\theta(nlgn)$ | $\theta(nlgn)$ | $\theta(nlgn)$ | Not in place sorting | Not in place sorting |
Heap | $\theta(nlgn)$ | $\theta(nlgn)$ | $\theta(nlgn)$ | $O(nlgn)$ | $\theta(nlgn)$ |