Insertion sort - Descending order

Learner picture Learner · Mar 8, 2013 · Viewed 24.5k times · Source

Sorry if its a basic question...

I am just trying to learn more on algorithms...

I wrote a simple code to perform insertion sort in ascending order, but for some reason I couldn't make it work to perform sort in descending order.

I tried changing the comparison key (while (i > 0 && a[i] > key) to (i > 0 && a[i] < key)).. it seems to work partially but the first element is not getting sorted, I get the below results..Can someone let me know where I am wrong?

1 11 10 9 5 4 3 2

public class InsertionSort {
    public static void main(String args[]) {
        int[] a = { 1,10,11,5, 9, 3, 2, 4 };
        // Loop through the entire array length. Consider you already have one
        // element in array, start comparing with
        // first element
        for (int j = 1; j < a.length; j++) {
            // Get the key (The value that needs to be compared with existing
            // values.
            int key = a[j];
            // Get the array index for comparison, we need to compare with all
            // other elements in the array with
            // key
            int i = j - 1;
            // While i > 0 and when key is less than the value in the array
            // shift the value and insert
            // the value appropriately.
            //System.out.println(j);
            while (i > 0 && a[i] < key) {
                a[i + 1] = a[i];
                i = i - 1;
                a[i + 1] = key;
            }
        }
        for (int k = 0; k < a.length; k++) {
            System.out.println(a[k]);
        }
    }
}

Answer

Daniel Fischer picture Daniel Fischer · Mar 8, 2013

You're never touching a[0] in

while (i > 0 && a[i] < key) {

so it isn't sorted into its due place. Use >= instead of >:

while (i >= 0 && a[i] < key) {

The same problem would occur when sorting in ascending order.