Home



2019/12 - DS&A #8: Insertion Sort

Howdy folks,

For Decembers post, we'll be diving into the Insertion Sort algorithm. It performs very similarly to the Selection Sort, so let's take a look:

public class InsertionSort {
    
    int[] valuesToSort;
    
    public InsertionSort(int size) {
        valuesToSort = new int[size];
    }
    
    public static void main(String[] args) {
         
        InsertionSort insertionSort = new InsertionSort(args.length);
        
        for(int i = 0 ; i < args.length; i++) {
            insertionSort.valuesToSort[i] = Integer.valueOf(args[i]);
            System.out.print(insertionSort.valuesToSort[i]+",");
        }
        
        System.out.println("");
        System.out.println("***");
        insertionSort.sortArray() ;
            
        System.out.println("Sorted");
        for(int i = 0 ; i < insertionSort.valuesToSort.length; i++) {
            System.out.print(insertionSort.valuesToSort[i]+",");
        }
    }
    

The above is just more setup/boilerplate as usual.

 


    public void sortArray() {
        
        for(int i = 1 ; i < valuesToSort.length; i++) {
                System.out.println("Iterating: " + i + " - " + valuesToSort[i]);
                int t = i - 1;
                int e = i;
                while(t >= 0 && valuesToSort[t] > valuesToSort[e]) {
                    travelBackOne(e);
                    t--;
                    e--;
                }    
                t = i;
                e = i;
        }        
    }
    

The sortArray method basically "grows" a list of values iteration by iteration, keeping it sorted before beginning a new iteration. It keeps it moving the newest value that it gained in the current iteration backwards in the sorted value list until that value is lower that the value to it's right, and greater than the value to it's left. If this doesn't make sense, you can also find some comparison graphics in this SO post.

 

    public void travelBackOne(int currentIndex) {
        int previousIndexValue = valuesToSort[currentIndex -1];
        int currentIndexValue = valuesToSort[currentIndex];
        
        System.out.println(previousIndexValue + " is going backwards, replacing " + currentIndexValue);
        valuesToSort[currentIndex] = previousIndexValue;
        valuesToSort[currentIndex -1] = currentIndexValue;
        
    }

}

This is just a convenience method for swapping value indices. Straightforward enough!

Good luck!

Marc