Chapter Two - Exercise 2.1-3

❓ Question

Rewrite the INSERTION-SORT procedure to sort into monotonically decreasing instead of monotonically increasing order.

💡 Answer

A monotonically decreasing order means starting from the highest element to the lowest: 23,22,21,20

The monotonically increasing order for insertion sort is:

1
2
3
4
5
6
7
8

INSERTION-SORT (A, n)
  for i = 2 to n
    key = A[i]
    j = i - 1
    while j > 0 AND A[j] > key
      A[j+1] = A[j]
      j = j - 1
    A[j + 1] = key

The monotonically decreasing order would be:

1
2
3
4
5
6
7
8

INSERTION-SORT (A, n)
  for i = n - 1 to 1
    key = A[i]
    j = i + 1
    while j < n AND A[j] < key
      A[j-1] = A[j]
      j = j + 1
    A[j - 1] = key