[Introduction to Algorithms, CLRS] Exercises 2.1-2

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.1-2 Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non- decreasing order.

Answer:

INSERTION-SORT (A)

1     for j = 2 to A.length 

2        key = A[j]

3         // Insert A[j] into the sorted sequence A[1..j-1].

4         i  =j - 1

5         while i >0 and A[i] < key

6             A[i+1] = A[i]

7             i = i - 1

8         A[i+1] = key