Insertion Sort: Difference between revisions
Jump to navigation
Jump to search
Line 6: | Line 6: | ||
=Overview= | =Overview= | ||
Insertion sort is a key comparison algorithm that receives an array of integers and sorts the values [[Sorting_Algorithms#In-place|in-place]]. It is an efficient algorithm for sorting a small number of elements. | Insertion sort is a [[Data_Structures_and_Algorithms#Comparison_Sort|key comparison algorithm]] that receives an array of integers and sorts the values [[Sorting_Algorithms#In-place|in-place]]. It is an efficient algorithm for sorting a small number of elements. | ||
=Algorithm= | =Algorithm= |
Revision as of 21:08, 5 August 2018
Internal
Overview
Insertion sort is a key comparison algorithm that receives an array of integers and sorts the values in-place. It is an efficient algorithm for sorting a small number of elements.
Algorithm
Insertion sort works as follows: we start from the left side of the array, and for each key, we insert it in the correct position in the already sorted sub-array that grows from left to right. The insertion is performed by scanning the sub-array from right to left in a while loop and swapping the elements until we reach the correct position of the key being handled.
public static void insertionSort(int[] a) {
//
// handle trivial cases when the array is empty or has just one element
//
//
// going forward, we assume the array has at least two elements
//
for(int i = 1; i < a.length; i ++) {
//
// if larger or equal, the key is in the right position, advance in the top level loop ...
//
if (a[i] >= a[i - 1]) {
continue;
}
//
// The key is smaller than the last one in the sorted subarray,
// send it through the subarray until it reaches the correct position.
// Use a different index variable.
int j = i - 1; // this is the first element of the sorted subarray
//
// order in which comparison expressions are evaluated is important,
// we use short-circuiting if j is negative
//
while(j >= 0 && a[j] > a[j + 1]) {
int key = a[j + 1];
a[j + 1] = a[j];
a[j] = key;
j --;
}
}
}