1.3 Insertion Sort
Category Algorithm
The implementation of insertion sort may not be as straightforward as bubble sort and selection sort, but its principle is probably the easiest to understand. Anyone who has played cards should be able to grasp it instantly. Insertion sort is a simple and intuitive sorting algorithm. It works by building a sorted sequence, and for the unsorted data, it scans from the end of the sorted sequence to the beginning, finds the appropriate position, and inserts it.
Similar to bubble sort, insertion sort also has an optimized version called binary insertion sort.
1. Algorithm Steps
Treat the first element of the sequence to be sorted as a sorted sequence and the second element to the last element as an unsorted sequence.
Scan the unsorted sequence from beginning to end, and insert each scanned element into the appropriate position in the sorted sequence. (If the element to be inserted is equal to an element in the sorted sequence, insert the element to be inserted after the equal element.)
2. Dynamic Demonstration
Code Implementation
JavaScript
Example
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Python
Example
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
Go
Example
func insertionSort(arr []int) []int {
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
Java
Example
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the array to avoid modifying the parameter content
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// Start inserting from the element at index 1, as the element at index 0 is already sorted
for (int i = 1; i < arr.length; i++) {
// Record the data to be inserted
int tmp = arr[i];
// Compare from the rightmost of the sorted sequence to find a number smaller than it
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// Insert if a smaller number is found
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
PHP
Example
function insertionSort($arr)
{
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$preIndex = $i - 1;
$current = $arr[$i];
while($preIndex >= 0 && $arr[$preIndex] > $current) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[$preIndex+1] = $current;
}
return $arr;
}
C
Example
void insertion_sort(int arr[], int len){
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
C++
Example
void insertion_sort(int arr[],int len){
for(int i=1;i<len;i++){
int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
C
Example
public static void InsertSort(int[] array)
{
for(int i = 1;i < array.length;i++)
{
int temp = array[i];
for(int j = i - 1;j >= 0;j--)
{
if(array[j] > temp)
{
array[j + 1] = array[j];
array[j] = temp;
}
else
break;
}
}
}
Swift
Example
for i in 1..<arr.endIndex {
let temp = arr[i]
for j in (0..<i).reversed() {
if arr[j] > temp {
arr.swapAt(j, j+1)
}
}
}
>
Original Source: https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md
Reference: https://en.wikipedia.org/wiki/Insertion_sort
#
-
** Mr.Sugarcane
* 843**[email protected]
I wrote a Lua version:
-- Insertion sort
function insert_sort(tab)
len = maxn_ex(tab)
for i=1,len-1 do
local j = i+1
while( j > 1 ) do
if(tab[j] < tab[j-1]) then
tab[j],tab[j-1] = tab[j-1],tab[j]
end
j = j -1
end
end
return tab
end
** Mr.Sugarcane
* 843**[email protected]
-
** kezhuoquan
* kez**[email protected]
Rust version:
/// Insertion sort
/// 0 ,..., j, i, ... n
/// 0 ,..., j: Sorted sequence, j = i ,..., n
/// i ,..., n: Unsorted sequence i = 1,2,3,4,5,...n
/// Compare the first element of the unsorted sequence (target) with the sorted sequence from right to left,
/// When target < array[j], swap target with array[j],
/// Otherwise, exit the loop
/// At this point, the first element of the unsorted sequence has been inserted into the sorted sequence
fn insert_sort<T:Ord + Debug>(array: &mut [T]) {
for i in 1..array.len() {
for j in (0..i).rev() {
if array[j + 1] < array[j] {
array.swap(j + 1, j);
} else {
break;
}
}
}
}
** kezhuoquan
* kez**[email protected]
-
** sujiujiu
* suj**[email protected]
Python's while loop can be better:
def insertionSort(arr):
for i in range(1, len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1], arr[preIndex] = arr[preIndex], arr[preIndex+1]
preIndex -= 1
return arr
Alternatively, using a for loop:
def insert_sort(arr):
for i in range(1, len(arr)):
current = arr[i]
for j in range(i, 0, -1):
if sort_list[j] < sort_list[j - 1]:
arr[j-1], arr[j] = arr[j], arr[j-1]
return arr
sujiujiu
Click to Share Notes
-
-
-
1.3 Insertion Sort