Algorithms Notes -Limitations of Simple Sorting

Def: Let (i, j) be an ordered pair of indices of an array A such that i < j and A[i] > A[j]. (i, j) is called an inversion in the array.

  • Swapping two elements that are out of place removes exactly one inversion.
  • A sorted array has zero inversions.

Note: Both the above assertions probably have good proofs. I can prove the second one by contradiction very prettily.

Technically, the running time of insertion sort is \mathcal{O}(I + n) where I is the number of inversions in the array. If the number of inversions is \mathcal{O}(n), insertion sort will run in linear time.

Thm: The average number of inversions in an array of n distinct numbers is \frac{n(n-1)}{4}.

Proof: Let $L$ be any list of numbers and L_{r} be the list in reverse order. Consider any pair of two numbers (x, y) with (without loss of generality) y > x in L. It must be true that (x, y) is an inversion in exactly one of L  and L_{r}. The total number of such pairs in any list L and its reverse L_{r} is \frac{n(n-1)}{2}. Hence, an average list has half this amount of inversions i.e \frac{n(n-1)}{4} inversions. \square

By this theorem, it is evident that insertion sort runs in quadratic time on average.

Thm: Any algorithm that sorts by exchanging adjacent elements requires \Omega(n^2) time on average.

Proof: The average number of inversions is initially \frac{n(n-1)}{4} = \Omega(n^2) as was established by the previous theorem. Since each swap removes at most one inversion, \Omega(n^2) swaps are required to sort the array. \square

This lower-bound proof is valid for an entire class of sorting algorithms that perform only adjacent exchanges. This includes, for example,

  • Insertion Sort
  • Bubble Sort
  • Selection Sort

This represents a limitation in ‘simple’ sorting algorithms and makes it clear that to achieve more efficiency we need to consider algorithms that do comparisons and exchanges between elements that are far apart. To run faster than quadratic time, an algorithm must eliminate more than one inversion per exchange.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s