Difference between revisions of "Complexities of Basic Sorting Algorithms"

Revision as of 14:35, 20 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(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)$

In-Place Sorting

When sorting happens within the same array, its called in-place sorting. All the above sorting except, merge sort are in-place sorting. In merge sort, we use an auxiliary array for merging two sub-arrays

Stable sorting

This matters only for arrays with same element repeated. For an element $a$ occurring at positions $x$ and $y$ in the original array, such that $x < y$, in the sorted array A[x] must be placed

@@ Line 50: / Line 50: @@
 |$\theta(n\lg n)$
 |}
+===In-Place Sorting===
+When sorting happens within the same array, its called in-place sorting. All the above sorting except, merge sort are in-place sorting. In merge sort, we use an auxiliary array for merging two sub-arrays
+===Stable sorting===
+This matters only for arrays with same element repeated. For an element $a$ occurring at positions $x$ and $y$ in the original array, such that $x < y$, in the sorted array A[x] must be placed
 {{Template:FBD}}
 [[Category:Notes & Ebooks for GATE Preparation]]
 [[Category: Algorithms & Data Structures]]