Giudoku Official Site
Insertion sort

Insertion sort is an easy sorting technique.

You start from the second element V[1] and loop until V[n]. For each loop, V[j] is saved in the variable key. At this point, we check the subarray V[0] ... V[j-1] and shift it one position right (starting from V[j-1]!) until we either shifted everything or we found a value that is greater than our key.
The key is thus put at the right position. It can be easily seen that at every loop, the subarray is sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Arrays;

public class InsertionSort
{
  public static void main(String[] x)
  {
    int[] v1 = {3, 6, 4, 1, 2, 7, 8, 5};
    
    System.out.println("Before sorting: " + Arrays.toString(v1));
    System.out.println("After sorting: " + Arrays.toString(insertionSort(v1)));
  }
  
  public static int[] insertionSort(int[] V)
  {
    for (int j = 1; j < V.length; j++)
    {
      int key = V[j];
      int i = j - 1;
      
      while (i >= 0 && V[i] > key)
      {
        V[i+1] = V[i];
        i--;
      }
      V[i+1] = key;
    }
    
    return V;
  }
}