Line 1: Line 1:
 
<metadesc>Complexities of basic sorting algorithms. Minimum no. of swaps required for sorting algorithms  </metadesc>
 
<metadesc>Complexities of basic sorting algorithms. Minimum no. of swaps required for sorting algorithms  </metadesc>
{|class="wikitable" style="text-align: center; color: black;"
+
{|class="wikitable" style="text-align: center; color: black;" width="85%"
 
! align="left"| Algorithm
 
! align="left"| Algorithm
 
! Worst Case
 
! Worst Case

Revision as of 18:21, 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(nlgn)$ $\theta(nlgn)$ 0 (when array is already sorted) $\theta(n^{2})$
Merge $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$ Not in place sorting Not in place sorting
Heap $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$ $O(nlgn)$ $\theta(nlgn)$




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(nlgn)$ $\theta(nlgn)$ 0 (when array is already sorted) $\theta(n^{2})$
Merge $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$ Not in place sorting Not in place sorting
Heap $\theta(nlgn)$ $\theta(nlgn)$ $\theta(nlgn)$ $O(nlgn)$ $\theta(nlgn)$




blog comments powered by Disqus