insertion sort
Created a sub-list from the first element that is our sorted list
Do:
Look at the next element
Compare with all elements in the sorted sub-list
Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Insert the value
While list is unsorted
and in java:
public class insertionSort{
public static void main(String[] args) {
int[] array = new int[]{35, 71, 1, 10, 4};
//for index 0, 1, 2, 3 and 4:
for (int index = 0; index < 5; index++) {
int valueToSort = array[index];
//so we can count backwards without losing our place:
int countBack = index;
//while we arent at the start, AND
//there is a bigger element PRIOR to the value to sort:
while (countBack > 0 && array[countBack - 1] > valueToSort) {
//swap the element with the prior element:
array[countBack] = array[countBack - 1];
//now count back one more, because we may have
//put our whole list out of whack with the move
//we just made:
countBack--;
}
//so once we get to this point,
//we EITHER are at the start, OR
//there was NO bigger element prior,
//which means this is the final resting place
//of the value to sort:
array[countBack] = valueToSort;
}
//to check result:
for(int index=0; index<5; index++) { System.out.println(array[index]); }
}
}