Once you click post assignment, learners in the selected class will immediately be able to see and complete this assignment

Back to Classroom

Insertion Sort

AP® Computer Science A (Java) Course

Engineers From These Top Companies and Universities Trust EXLskills

1M+ Professionals | 100+ Institutions

This is the EXLskills free and open-source AP® (Advanced Placement®) Java Course. It guides learners via explanation, demonstration, and thorough practice, from no more than a basic understanding of Java, to a moderate level of essential coding proficiency. It is a substantial amount of coursework that represents a typical year of high school-level study or a semester of a University computer science course. This course may also be used to prepare for the AP® Computer Science A exam.

Is this course FREE?

Yes, this a 100% free course that you can contribute to on GitHub here!

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.

publicvoidinsertionSort(int[] paramOne){
for (int j = 1; j < paramOne.length; j++)
{
int insertItem = paramOne[j];
int k = j - 1;
while (k >= 0 && insertItem < 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 */)?