Line 5: Line 5:
 
! Average Case
 
! Average Case
 
! Best Case
 
! Best Case
 +
! Min. no. of swaps
 +
! Max. no. of swaps
 
|-
 
|-
 
|Bubble
 
|Bubble
 +
|$\theta(n^{2})$
 +
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
Line 14: Line 18:
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 +
|$\theta(n^{2})$
 +
|0 (when array is already sorted)
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|-
 
|-
Line 20: Line 26:
 
|$\theta(n^{2})$
 
|$\theta(n^{2})$
 
|$\theta(n)$ (when array is sorted)
 
|$\theta(n)$ (when array is sorted)
 +
|0 (when array is already sorted)
 +
|$\theta(n^{2})$
 
|-
 
|-
 
|Quick
 
|Quick
Line 25: Line 33:
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 +
|0 (when array is already sorted)
 +
|$\theta(n^{2})$
 
|-
 
|-
 
|Merge
 
|Merge
Line 30: Line 40:
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 +
|Not in place sorting
 +
|Not in place sorting
 
|-
 
|-
 
|Heap
 
|Heap
 +
|$\theta(nlgn)$
 +
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$
 
|$\theta(nlgn)$

Revision as of 21:49, 8 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)$ $\theta(nlgn)$ $\theta(nlgn)$




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




blog comments powered by Disqus