insertion sorting algorithm brings the largest number to the bottom

Question

I´m working on insertion sorting a bunch of numbers but I just can´t wrap my head around it. I´m pretty sure the "j = i - 1" is wrong and a bunch of other things, and I´d really appreciate it if you guys could point out my mistakes so I can fix them.

public class temp {
  public static void main(String[] args) {
    int numbrid[] = {2, 5, 9, 7, 1, 4, 3, 8, 6};
    System.out.println("before:");
    int i, j, k;
    for (i = 0; i < numbrid.length; i++) {
        System.out.println(numbrid[i]);
    }
    //sorting
    System.out.println("after:");
    for (i = 1; i < numbrid.length; i++) {
        j = i - 1;
        while (numbrid[i] < numbrid[j]) {
            k = numbrid[i];
            numbrid[i] = numbrid[j];
            numbrid[j] = k; // swaps their places
        }
    }
    for ( i = 0; i < numbrid.length; i++ ) {
        System.out.println(numbrid[i]);
    }
  }
}

Edit: all this does is it takes the largest number and brings it to the bottom

Answer 1

A few problems in your for loop:

1. Insertion has to use just 1 input per iteration (of the outside for), hence you have to assign the value to your temp variable before you get into your while

   for (i = 1; i < numbrid.length; i++) {
     k = numbrid[i];
   

2. Step on to the while loop with replacing the next number with the previous one till you reach your temp number (till your numbrid[j] > k)

   while ((j > -1) && (numbrid[j] > k)) {
   numbrid[j + 1] = numbrid[j];
   j--;
   }
   

3. Assign your temp value to the next element in your array

   numbridj + 1] = k;
   

4. Move on with your for loop

Hence, your for loop becomes:

...
for (i = 1; i < numbrid.length; i++) {
    k = numbrid[i];
    j = i - 1;
    while ((j > -1) && (numbrid[j] > k)) {
        numbrid[j + 1] = numbrid[j];
        j--;
    }
    numbrid[j + 1] = k;
}
...

Answer 2

I see two errors:

• You musn't swap j and i elements but j and j+1
• You are forgetting to decrease j

oooh @PopoFibo anticipated :( well I'll post anyway..