Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 8: | Line 8: | ||
! Max. no. of swaps | ! Max. no. of swaps | ||
|- | |- | ||
| − | |Bubble | + | |[http://en.wikipedia.org/wiki/Bubble_sort Bubble] |
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
| Line 15: | Line 15: | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|- | |- | ||
| − | |Selection | + | |[http://en.wikipedia.org/wiki/Selection_sort Selection] |
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
| Line 22: | Line 22: | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|- | |- | ||
| − | |Insertion | + | |[http://en.wikipedia.org/wiki/Quick_sort Insertion] |
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
| Line 29: | Line 29: | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|- | |- | ||
| − | |Quick | + | |[http://en.wikipedia.org/wiki/Quick_sort Quick] |
|$\theta(n^{2})$ (when array is sorted, and pivot taken from one end) | |$\theta(n^{2})$ (when array is sorted, and pivot taken from one end) | ||
|$\theta(n\lg n)$ | |$\theta(n\lg n)$ | ||
| Line 36: | Line 36: | ||
|$\theta(n^{2})$ | |$\theta(n^{2})$ | ||
|- | |- | ||
| − | |Merge | + | |[http://en.wikipedia.org/wiki/Merge_sort Merge] |
|$\theta(n\lg n)$ | |$\theta(n\lg n)$ | ||
|$\theta(n\lg n)$ | |$\theta(n\lg n)$ | ||
| Line 43: | Line 43: | ||
|Is not in-place sorting | |Is not in-place sorting | ||
|- | |- | ||
| − | |Heap | + | |[http://en.wikipedia.org/wiki/Heap_sort Heap] |
|$\theta(n\lg n)$ | |$\theta(n\lg n)$ | ||
|$\theta(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)$ |
When sorting happens within the same array, its called in-place sorting. All the above sorting except, merge sort are in-place sorting. In merge sort, we use an auxiliary array for merging two sub-arrays
This matters only for arrays with same element repeated. If $A[x] = A[y]$, in the original array such that $x<y$, then in the sorted array, $A[x]$ must be placed at position $u$ and $A[y]$ must be placed at position $v$, such that $u<v$. i.e.; the relative positions of same value elements must be same in the sorted array as in the input array, for the sorting algorithm to be stable. In most cases stability depends on the way in which algorithm is implemented. Still, its not possible to implement heap sort as a stable sort.
| 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)$ |
When sorting happens within the same array, its called in-place sorting. All the above sorting except, merge sort are in-place sorting. In merge sort, we use an auxiliary array for merging two sub-arrays
This matters only for arrays with same element repeated. If $A[x] = A[y]$, in the original array such that $x<y$, then in the sorted array, $A[x]$ must be placed at position $u$ and $A[y]$ must be placed at position $v$, such that $u<v$. i.e.; the relative positions of same value elements must be same in the sorted array as in the input array, for the sorting algorithm to be stable. In most cases stability depends on the way in which algorithm is implemented. Still, its not possible to implement heap sort as a stable sort.
GATECSE