Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 50: | Line 50: | ||
|$\theta(n\lg n)$ | |$\theta(n\lg n)$ | ||
|} | |} | ||
| + | |||
| + | ===In-Place Sorting=== | ||
| + | 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 | ||
| + | |||
| + | ===Stable sorting=== | ||
| + | This matters only for arrays with same element repeated. For an element $a$ occurring at positions $x$ and $y$ in the original array, such that $x < y$, in the sorted array A[x] must be placed | ||
{{Template:FBD}} | {{Template:FBD}} | ||
[[Category:Notes & Ebooks for GATE Preparation]] | [[Category:Notes & Ebooks for GATE Preparation]] | ||
[[Category: Algorithms & Data Structures]] | [[Category: Algorithms & Data Structures]] | ||
| 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. For an element $a$ occurring at positions $x$ and $y$ in the original array, such that $x < y$, in the sorted array A[x] must be placed
| 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. For an element $a$ occurring at positions $x$ and $y$ in the original array, such that $x < y$, in the sorted array A[x] must be placed
GATECSE