import java.util.Arrays;

/**
 *
 * @author Javargon
 *
 * www.javargon.com
 *
 * Problem Statement : Rewrite the Insertion-Sort procedure to sort
 * into non-increasing instead of non-decreasing order.
 * Exercise 2.1-2, Introduction to Algorithms, Cormen
 *
 */
public class InsertionSortDecreasingDemo {

	public static void main(String[] args) {
		int[] a = new int[]{31,41,59,26,41,58};

		for(int i=1; i<a.length; i++) {
			int key = a[i];
			int j = i-1;

			while(j >= 0 && a[j] < key) {
				a[j+1] = a[j];
				j--;
			}
			a[j+1] = key;
		}

		System.out.println("Decreaing order -> "+Arrays.toString(a));
	}

}