Line 55: Line 55:
  
 
===Stable sorting===
 
===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  
+
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$.
  
 
{{Template:FBD}}
 
{{Template:FBD}}
 
[[Category:Notes & Ebooks for GATE Preparation]]
 
[[Category:Notes & Ebooks for GATE Preparation]]
 
[[Category: Algorithms & Data Structures]]
 
[[Category: Algorithms & Data Structures]]

Revision as of 14:39, 20 December 2013

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)$

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. 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$.




blog comments powered by Disqus
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)$

In-Place Sorting[edit]

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[edit]

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$.




blog comments powered by Disqus