2.7 The Cost of Exchange Sorting

Here is a summary for the cost of Insertion Sort, Bubble Sort, and Selection Sort in terms of their required number of comparisons and swaps in the best, average, and worst cases. The running time for each of these sorts is Θ(n2)\Theta(n^2) in the average and worst cases.

Insertion Bubble Selection
Comparisons:
Best case Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2)
Average case Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2)
Worst case Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2)
Swaps:
Best case 00 00 Θ(n)\Theta(n)
Average case Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2) Θ(n)\Theta(n)
Worst case Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2) Θ(n)\Theta(n)

The remaining sorting algorithms presented in this tutorial are significantly better than these three under typical conditions. But before continuing on, it is instructive to investigate what makes these three sorts so slow. The crucial bottleneck is that only adjacent records are compared. Thus, comparisons and moves (for Insertion and Bubble Sort) are by single steps. Swapping adjacent records is called an exchange. Thus, these sorts are sometimes referred to as an exchange sort. The cost of any exchange sort can be at best the total number of steps that the records in the array must move to reach their “correct” location. Recall that this is at least the number of inversions for the record, where an inversion occurs when a record with key value greater than the current record’s key value appears before it.

2.7.1 Analysis

2.7.2 Review questions: Exchange sort

Answer TRUE or FALSE.

Consider an array AA of nn records each with a unique key value, and ARA_R the same array in reverse order. Any given pair of records must be an inversion in exactly one of AA or ARA_R.

  • Any given pair of records with different values is either in order, or not in order.
  • Being out of order is called an inversion.
  • If your pair is in order in some array, then it must be out of order in the reverse.

Answer TRUE or FALSE.

Consider an array AA of nn records each with a unique key value, and ARA_R the same array in reverse order. There are a certain number of pairs, where an arbitrary position ii and position jj is a pair. Between these two arrays, exactly half of these pairs must be inverted.

  • Any given pair of records with different key values is either in order, or not in order.
  • Being out of order is called an inversion.
  • Any given pair must be inverted in exactly one of these arrays.
  • So every pair must be inverted in either AA or ARA_R.

The average number of inversions in an array of nn records is n(n−1)/4n(n-1)/4. This is:

  • n(n−1)/4=n2/4−n/4n(n-1)/4 = n^2/4 - n/4.
  • From the rules on asymptotic analysis, Θ(n2/4−n/4)\Theta(n^2/4 - n/4) is Θ(n2)\Theta(n^2)

An exchange sort is:

  • Most of the sorts that we study swap records.
  • Insertion Sort is not the only exchange sort.
  • An “exchange” means a swap of adjacent records.

An inversion is:

  • We have not used “inversion” to refer to a type of sort.
  • While “inversions” are related to swaps (since ultimately a swap is needed to undo an inversion), it is not a swap.
  • Inversion refers to an instance of a record being out of order.

How many ways can nn distinct values be arranged?

  • There are nn ways to pick the first record.
  • That leaves n−1n-1 ways to pick the second record.
  • This means that there are n*(n−1)n * (n-1) ways to pick the first two records.
  • And so on.

If I is the number of inversions in an input array of n records, then Insertion Sort will require how many swaps?

  • An inversion requires a swap to undo it.
  • The number of comparisons done by an algorithm is generally different from the number of swaps.

The total number of pairs of records among nn records is:

  • There are nn ways to pick the first record in the pair.
  • This leaves n−1n-1 ways to pick the second record.
  • We consider pair (A, B) to be the same as pair (B, A).