-3

This is my algorithm for Insertion Sort. It always skips the first element in the array.

Example :

Input : 5 8 4 9
Output : 5 4 8 9

Here is the code.

import java.util.*;

class InsertionSort {
    public void InsertAsc(int A [],int n)
    {
        for (int j=1; j<n; ++j){
            int key=A[j];
            int i=j-1;
            while(i>0 &&A[i]>key)
            {
                A[i+1]=A[i];            
                i=i-1;
            }
            A[i+1]=key;
        }
        System.out.println("The sorted numbers are"+Arrays.toString(A));
    }

    public static void main(String args[])
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the numbers of number that you want to sort");
        int n=scan.nextInt();
        int A[]=new int[n];
        System.out.println("Enter the numbers that you want to sort");
        for(int i=0;i<n;i++)
        {
            A[i]=scan.nextInt();
        }
        
        System.out.println("The numbers are"+Arrays.toString(A));
        InsertionSort ob = new InsertionSort();
        ob.InsertAsc(A,n);
    }
}
Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Subodh Poudel
  • 35
  • 5
  • 1
    Change `i>0` to `i>=0` so it might actually be able to insert in the first position of the array. --- Next time, please you use **debugger**. See "[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149)" and "[How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/)". – Andreas Apr 20 '20 at 06:42
  • while ( (i > -1) && ( A[i] > key ) ) Try this – Niroshan Ratnayake Apr 20 '20 at 06:47
  • 1
    Arrays in Java are `0`-based, meaning that the 'first' element on index 0. So by starting at index=1, you are skipping the first element. – TreffnonX Apr 20 '20 at 08:41

1 Answers1

-1

Pay close attention to this line while(i>0 &&A[i]>key) your variable i needs to go to index 0 as well and in your case it isn't so i>=0 fixes it.

Also I hope you can visualize how the algorithm is working-

  1. You go from index 1 to n-1 in your array with the variable j
    • You store the element at index j in a key variable so that you don't lose the value
    • You check the indexes from 0 to j-1 with your variable i and keep moving the elements greater than key one step ahead
    • You thus stop at an index i containing an element less than or equal to the key or you stop at -1 if all elements from 0 to i-1 are greater than key
    • Finally you place your key element at index i+1
himanshu1495
  • 1
  • 2