Insertion sort - Descending order

Question

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]);
        }
    }
}

Solution 1

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.

Solution 2

The first element in the array is a[0]. You're not comparing it anywhere.

Solution 3

public static void insertionSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int curNumber = arr[i];
            int curIndex = i-1;
            while ( curIndex >= 0 && arr[curIndex] < curNumber)
            {
                arr[curIndex+1] = arr[curIndex];
                curIndex--;
            }
            arr[curIndex+1] = curNumber;
        }
    }

Solution 4

Start from 0 with array a[] to reach the first element a[0]. So first element in a[j] will be a[0] and not a[1];

View more solutions

Comments

[Learner]

Sorry..My bad...my test data was bad that I didn't realize that I am not touching the first element in array when doing ascending order..

[Azeem]

If I'm not wrong, shouldn't the line a[i+1] = key come out of the while loop?

[Daniel Fischer]

@Azeem For correctness of the algorithm, it doesn't matter. For efficiency, you're right, it should come after the while loop to have fewer writes to the array.

[Azeem]

@DanielFischer my bad, you are right. I didn't have a deep look, I just took a look and found something was wrong here.

[Suraj Kumar]

Please don't post only code as an answer, but also provide an explanation of what your code does and how it solves the problem of the question. Answers with an explanation are usually of higher quality and are more likely to attract upvotes.