Arjun Suresh (talk | contribs) m (Arjun Suresh moved page Complexity of Basic Sorting Algorithms to Complexities of Basic Sorting Algorithms) |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | + | <metadesc>Complexities of basic sorting algorithms. Minimum no. of swaps required for sorting algorithms </metadesc> | |
{|class="wikitable" style="text-align: center; color: black;" | {|class="wikitable" style="text-align: center; color: black;" | ||
! align="left"| Algorithm | ! align="left"| Algorithm | ||
| 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)$ |
GATECSE