Insertion sort is similar to how you would organize a deck of cards. You would start with the first card and then compare it to the values of the other cards, using the second card as a key value. In an insertion sort there are two subarrays, the part that is sorted at the beginning and then the remaining unsorted subarray. Each time the list is iterated through the next unsorted value is picked, and that value is used as a key. From that point, it moves all the elements in the sorted subarray that are greater than the key that is one ahead of their position, and then that key is "inserted" into the sorted subarray. This process continues until all of the unsorted values are sorted. Insertion is an easy algorithm to code, but it is bad for large sets of data. It's mainly useful when there are a small number of elements in the list of if most of the elements are already sorted.
public class InsertionSearch {
public static void main (String [] args){
int []values = {3,1,9,5,6,2,2,7,8,11};
insertionSort(values);
}
public static void insertionSort (int values[ ]) {
int arrlen = values.length;
for (int i = 0; i < arrlen; i++) {
int currentValue = values[i];
int compare = i-1;
while (compare >= 0 && values[compare] > currentValue ){
values[compare+1] = values[compare];
compare = compare -1;
}
values[compare +1] = currentValue;
}
for (int i = 0 ;i< values.length; i++){
System.out.print(" "+values[i]);
}
}
}
1 2 2 3 5 6 7 8 9 11