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

<metadesc>Complexities of basic sorting algorithms. Minimum no. of swaps required for sorting algorithms  </metadesc>
{|class="wikitable" style="text-align: center; color: black;" width="85%"
! 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(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)$
|}



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