Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 5: | Line 5: | ||
! Average Case | ! Average Case | ||
! Best Case | ! Best Case | ||
| + | ! Min. no. of swaps | ||
| + | ! Max. no. of swaps | ||
|- | |- | ||
|Bubble | |Bubble | ||
| + | |$\theta(n^{2})$ | ||
| + | |$\theta(n^{2})$ | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
| Line 14: | Line 18: | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
| + | |$\theta(n^{2})$ | ||
| + | |0 (when array is already sorted) | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|- | |- | ||
| Line 20: | Line 26: | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|$\theta(n)$ (when array is sorted) | |$\theta(n)$ (when array is sorted) | ||
| + | |0 (when array is already sorted) | ||
| + | |$\theta(n^{2})$ | ||
|- | |- | ||
|Quick | |Quick | ||
| Line 25: | Line 33: | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
| + | |0 (when array is already sorted) | ||
| + | |$\theta(n^{2})$ | ||
|- | |- | ||
|Merge | |Merge | ||
| Line 30: | Line 40: | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
|$\theta(nlgn)$ | |$\theta(nlgn)$ | ||
| + | |Not in place sorting | ||
| + | |Not in place sorting | ||
|- | |- | ||
|Heap | |Heap | ||
| + | |$\theta(nlgn)$ | ||
| + | |$\theta(nlgn)$ | ||
|$\theta(nlgn)$ | |$\theta(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)$ | $\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)$ | $\theta(nlgn)$ | $\theta(nlgn)$ |
GATECSE