View source for Complexities of Basic Sorting Algorithms ← Complexities of Basic Sorting Algorithms


{|class="wikitable" style="text-align: center; color: black;"
! align="left"| 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)$
|$\bigo(nlgn)$
|}



<div class="fb-like"  data-layout="standard" data-action="like" data-show-faces="false" data-share="true"></div>


<div class="fb-share-button"  data-type="button_count"></div>



<disqus/>
[[Category: CS Notes]]
[[Category: Algorithms & Data Structures]]
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)$	$\bigo(nlgn)$