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
