0

Why is this insertion sort giving me the wrong answer, whereas i'm getting the right answer when I do it the way the comment lines specify?What is the difference?

    public class Solution
    {

    public static void main(String[] args) 
    {

    Scanner s=new Scanner(System.in);
    int i,j,n,sk=0; //consider another variable k
    int a[]=new int[20];
    n=s.nextInt();
    for(i=0;i<n;i++)
        a[i]=s.nextInt();
    for(i=1;i<n;i++)
    {   j=i-1;
        //adding k=a[i]
    while((j>=0)&&a[j]>a[i]) //a[j]>k instead of the condition a[j]>a[i]
    {   sk++;
        a[j+1]=a[j];
        j--;
    }
       a[j+1]=a[i];
       //a[j+1]=k instead of the previous line.       
    }
    for(i=0;i<n;i++)
    System.out.println(a[i]);
    }
    }
Senthilnathan
  • 1
  • 1

2 Answers2

3

this line a[j+1]=a[j];

Consider the array = {5,2,3} when i = 1, j = 0, 

 while((j>=0)&&a[j]>a[i]) //a[j]>k instead of the condition a[j]>a[i]
        {   sk++;
        a[j+1]=a[j];   // a[1] = a[0]
            j--;   // j becomes -1 out of the loop 
        }
  // Array becomes {5,5,3} after while loop, we lost 2 
           a[j+1]=a[i];   // again  a[0] is just getting initialized to a[1] 
                                           //which are same
           //a[j+1]=k instead of the previous line.  **// K will have previous 
                                              a[1]**      
        }

You already updated a[1] when you did a[j+1]=a[j] and then outside the while loop you are again assigning a[1] = a[1], however, k will store previous a[1] value, not the updated one

Isha Agarwal
  • 420
  • 4
  • 12
0

To make it simple, in your solution, you are editing your variables by reference whereas the correct solution is to pass them by value.

When you pass your variables by reference, editing one value would be the same as editing the second.

Here is a simple code which should help you to understand:

public class Main {
    public static void main(String[] args) {
        Foo foo = new Foo();

        int valueToAdd = 5;
        // foo.a will not be modified because we set the parameter by value
        editTestByValue(foo.a, valueToAdd);
        System.out.println(foo.a); // prints 1


        editTestByReference(foo, valueToAdd);
        // foo.a will be modified because we set the parameter by reference
        System.out.println(foo.a); // prints 6
    }

    public static void editTestByValue(int a, int valueToAdd){
        a += valueToAdd;
    }

    public static void editTestByReference(Foo foo, int valueToAdd){
        foo.a += valueToAdd;
    }
}

class Foo {
     public int a = 1;
}

You use the same thing by using an array instead of a class.

For more information, you can check this What's the difference between passing by reference vs. passing by value?

Hope it helped !

Olivier Penas
  • 1