Difference between revisions of "Complexities of Basic Sorting Algorithms"

Line 19: Line 19:
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
−
|$\theta(n)$
+
|$\theta(n)$ (when array is sorted)
 
|-
 
|-
 
|Quick
 
|Quick
−
|$\theta(n^{2})$
+
|$\theta(n^{2})$ (when array is sorted, and pivot taken from one end)
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$

Revision as of 12:19, 8 December 2013

Algorithm Worst Case Average Case Best Case
Bubble $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$
Selection $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$
Insertion $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n)$ (when array is sorted)
Quick $\theta(n^{2})$ (when array is sorted, and pivot taken from one end) $\theta(nlgn)$ $\theta(nlgn)$
Merge $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$
Heap $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$
Retrieved from "https://gatecse.in/w/index.php?title=Complexities_of_Basic_Sorting_Algorithms&oldid=1226"
Algorithm Worst Case Average Case Best Case
Bubble $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$
Selection $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$
Insertion $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n)$ (when array is sorted)
Quick $\theta(n^{2})$ (when array is sorted, and pivot taken from one end) $\theta(nlgn)$ $\theta(nlgn)$
Merge $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$
Heap $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$