CODEWITHSUNDEEP
javasortinginsertion-sort
Mayank Vaid
Mayank Vaid

Reputation: 329

Insertion Sort algorithm not working as expected

My insertion sort code is:

class insertionsort
{
    public static void main(String s[])
    {
        int []A={12,5,8,87,55,4};
        int []R=sort(A);
        for(int i=0;i<A.length;i++)
        {
            System.out.println(R[i]);
        }
    }
    static int[] sort(int A[])
    {
        int key,i,j;
        for(j=1;j<A.length;j++)
        {
            key=A[j];
            i=j-1;
            while(i>=0 && A[j]<A[i])
            {
                A[j]=A[i];
                i--;
            }
            A[i+1]=key;
        }
        return A;
    }
}

But result is not correct. However, if I replace A[j] with key in while loop condition and A[j] with A[i+1] in while loop body, code generates the correct result. Is there any difference between A[j] and key and A[j] and A[i+1]?

Upvotes: 1

Views: 83

Answers (1)

Miljen Mikic
Miljen Mikic

Reputation: 15261

Correct code:

    static void sort(int A[])
    {
         for(int j = 1; j < A.length; j++)
         {
            int key = A[j];
            int i = j;
            while(i > 0 && A[i-1] > key)
            {
                A[i] = A[i-1];
                i--;
            }
            A[i] = key;
         }
    }

Note that you don't have to return anything since the method itself changes the input array.

Q: Is there any difference in A[j] and key or A[j] and A[i+1]?

Of course. The whole point of the insertion sort algorithm is that it exchanges the current element with all elements on the left hand side that are greater than it. Imagine it like rearranging cards in your hand. In your original version, j is fixed in the inner loop and rearranging does not happen.

Upvotes: 2

Related Questions