insertion sort using 2 arrays java

Question

I am trying to figure out how to use insertion sort to sort an array of ints. I need to take values from the original array and put them into the new array. I will show what code I have, but I have hit a brick wall and cannot figure out how this sorting method works.`

import java.util.Arrays;
public static void main(String[] args)
{
int[] orgArray = {5,4,1,6,3,144,2,14};
    int[] newArray = new int[orgArray.length];
    int currentNum=0;
    for(int x=1; x<orgArray.length; x++)
    {
        if(x==1)
            newArray[0]=orgArray[0];
        else
            for(int y=x;y>0; y--)
            {
                currentNum = orgArray[x];
                if(newArray[y]<currentNum)
                {
                    for(int z=orgArray.length-2;z>y;z--)
                        newArray[z]=newArray[z+1];
                    newArray[x]=orgArray[x];
                }

            }
    }
    System.out.println("Ascending order : " + Arrays.toString(newArray));
}

The output is:

Ascending order : [5, 0, 14, 14, 14, 14, 14, 14]

Apparently last year's class got this program easily, but for me, this was a 3 day program until @Elliot_Frisch helped out. — no_skillz
– no_skillz, Commented Apr 3, 2014 at 5:07

Elliott Frisch · Accepted Answer · 2014-04-02 01:59:30Z

5

When looking at Insertion Sort, first consider the algorithm -

Insertion sort animation example

From the animation, you should be able to tell that it's in-place. With that in mind, I think you wanted something like this -

int[] orgArray = { 5, 4, 1, 6, 3, 144, 2, 14 };
int[] newArray = new int[orgArray.length];
// Copy the original array.
System.arraycopy(orgArray, 0, newArray, 0,
    orgArray.length);
for (int x = 1; x < newArray.length; x++) {
  int currentNum = newArray[x]; // <-- the current number changes on every loop
  int y = x;

  // The actual condition on which to shift up!
  for (; y > 0 && newArray[y - 1] > currentNum; y--) {
    newArray[y] = newArray[y - 1];
  }
  // All shifts done, insert the correct place.
  newArray[y] = currentNum;
}
System.out.println("Ascending order : "
    + Arrays.toString(newArray));

Which outputs,

Ascending order : [1, 2, 3, 4, 5, 6, 14, 144]

answered Apr 2, 2014 at 1:59

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

no_skillz Over a year ago

I would upvote your comment, but I don't have enough reputation. I didn't know that System.arraycopy(); existed. Thanks for your help!

Collectives™ on Stack Overflow

insertion sort using 2 arrays java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related