Insertion Sort

Sorting

Insertion Sort

🙋 Need help? Ask an expert now!

Insertion sort is a more efficient type of sort as it passes through an array only once and puts each element in its correct location as it is analyzed. This method is similar to organizing a handful of playing cards where you pick up each card and insert it into its correct position in your hand of organized cards. Insertion sort divides the array or ArrayList into two sub-arrays; one is always sorted and increases in size as the sort continues, like the organized cards in your hand. The second sub-array is unsorted and contains all the elements yet to be inserted into the first sub-array, like the random cards you are picking up. The second sub-array decreases in size as the sort goes on, while the first sub-array increases in size. Let's take a look at the insertion sort below.

InsertionSortExample.java
package exlcode;

public class InsertionSortExample {

  public static void main(String[] args) {
    int[] exampleVariableOne = {17, 5, 21, 8, 19, 2, 23, 15, 4, 13};
    insertionSort(exampleVariableOne);
    System.out.println("Sorted Values: ");
    for (int val : exampleVariableOne) {
      System.out.print(val + " ");
    }
  }

  public static void insertionSort(int[] parameterOne) {
    for (int j = 1; j < parameterOne.length; j++) {
      int k = j;
      while (k > 0 && parameterOne[k - 1] > parameterOne[k]) {
        // looks at the array in order and moves every value
        // to where they should be starting from index 0
        int temp = parameterOne[k - 1];
        parameterOne[k - 1] = parameterOne[k];
        parameterOne[k] = temp;
        k--;
      }
    }
  }
}

Check out the java.util.Array class when you are ready to start using the pre-written searches and sort methods to save yourself time. Just make sure you always know the correct parameters and syntax. Although you are not writing your own sort methods in the future, you will need to know how one works and be able to decipher the code. In fact, you should be familiar with all four search and sort methods covered in the course.

Edit Me on GitHub!

Application Question

Consider the following insertion sort method:

public void insertionSort(int[] paramOne){
  for (int j = 1; j &#60; paramOne.length; j++)
  {
    int insertItem = paramOne[j];
    int k = j - 1;

    while (k &#62;= 0 &#38;&#38; insertItem &#60; paramOne[k]){
      paramOne[k + 1] = paramOne[k];
      k—-;
    }
    paramOne[k + 1] = insertItem;
    /* end of for loop */
  }
}

Assume that insertionSort is called with the array {5,4,3,2,1}. What will the value of paramOne be after two passes of the outer loop (i.e., when j = 2 at the point indicated by /* End of outer loop */)?




...

You've Reached the End of this Course! ğŸŽ“ğŸŽ‰

Great work, are you ready to learn more?

View More Courses