Insertion Sort: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
Line 16: | Line 16: | ||
for(int i = 1; i < a.length; i ++) { | for(int i = 1; i < a.length; i ++) { | ||
if (a[i] | |||
// if larger or equal, the key is in the right position, advance ... | |||
if (a[i] >= a[i - 1]) { | |||
continue; | |||
} | |||
} | } | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> |
Revision as of 20:33, 5 August 2018
Internal
Overview
Insertion sort receives an array of integers and sorts the values in-place. It 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 ...
if (a[i] >= a[i - 1]) {
continue;
}
}
}