External Exam Download Resources Web Applications Games Recycle Bin

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]); }
    }
}