Insertion Sort

Published

The following post is derived from notes taken while reading through this textbook .

For the purpose of this post, we will use this array of colors. Each element of the array is an object that holds the name of a color. The array is, currently, not sorted.

Insertion Sort:

The insertion sort algorithm is fairly straight-forward, but I will still explain it through the comments. The code for the insertion sort algorithm is as follows.

    
        /**
        * This is an example of an insertion sort algorithm with
        * a runtime of O(n²).
        *
        * Credits to the textbook linked in the post for the basic algorithm
        * that I have altered for the purposes of this post.
        *
        * @param arr An array of Color objects to sort.
        */
        public static void insertionSort(final Color[] arr) {
            // Start at the first element and loop through all of them.
            for(int i=1;i<arr.length;i++) {
                // Save the current color to a temp variable.
                Color temp = arr[i];
                int j = i - 1;

                // While temp's name is greater than the element at (tempsPosition - 1)
                // continue swapping temp with the element at (tempsPosition - 1).
                while((j >= 0) && (temp.getName().compareTo(arr[i].getName()) == 1))) {
                    arr[j + 1] = arr[j--];
                }

                arr[j + 1] = temp;
            }
        }
    

The, simplified, process of the insertion sort when applied to our example array is below. You can safely ignore this if you understand the algorithm, but it may prove useful if you don't understand it and would like a, slightly, long walkthrough of the basic steps.

The sorted array above is the result of applying the insertion sort to the example array at the beginning of this post. If you follow along with my, slightly, long list of steps above, then you should have an array of colors that match the one above.

Additional Information: