[Solved]: How can I quantify the number of swaps required for insertion sort?

Problem Detail: 

Based on the Wikipedia implementation of insertion sort:

Given an input array $A$:

for i ← 1 to length(A)     j ← i     while j > 0 and A[j-1] > A[j]         swap A[j] and A[j-1]         j ← j - 1 

is there a way to quantify how many swaps are needed to sort the input list? It's $O(n^2)$, but I want a more precise bound. A perfectly sorted array clearly needs no swaps (so insertion sort is $\Omega(n)$), while a completely reversed array requires something on the order of $n^2$ swaps, but how do we quantify the number of swaps?

Asked By : David Faux

Answered By : Yuval Filmus

It is a classic exercise to relate the running time of insertion sort to the number of inversions in the input. An inversion is a pair of indices $i < j$ such that $A[i] > A[j]$. The number of comparisons made by insertion sort when there are $I$ inversions is always between $I$ and $I+n-1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21455

3.2K people like this

 Download Related Notes/Documents