Line 32: Line 32:
 
|$\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)$
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
 
|0 (when array is already sorted)
 
|0 (when array is already sorted)
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|-
 
|-
 
|Merge
 
|Merge
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
 
|Is not in-place sorting
 
|Is not in-place sorting
 
|Is not in-place sorting
 
|Is not in-place sorting
 
|-
 
|-
 
|Heap
 
|Heap
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
|$O(nlgn)$
+
|$O(n\lg n)$
|$\theta(nlgn)$
+
|$\theta(n\lg n)$
 
|}
 
|}
  

Revision as of 18:29, 9 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)$




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




blog comments powered by Disqus