The path of learning for intermediate programmers the use of insertion sort

Let’s introduce the source code of various languages ​​for easy-to-understand insertion sort, as follows:

Although the code implementation of insertion sort is not as simple and rude as bubble sort and selection sort, its principle should be the easiest to understand, because anyone who has played poker should be able to understand it in seconds. Insertion sort is one of the simplest and most intuitive sorting algorithms. Its working principle is to construct an ordered sequence. For unsorted data, scan from back to front in the sorted sequence, find the corresponding position and insert it. Insertion sort, like bubble sort, also has an optimization algorithm called split-half insertion.

1. Algorithm steps

The first element of the first to-be-sorted sequence is regarded as an ordered sequence, and the second to the last element is regarded as an unsorted sequence.

Scans the unsorted sequence from beginning to end, inserting each element scanned into the appropriate position of the sorted sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)

2. Code implementation

JavaScript implementation

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 implementation

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 implementation

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 instance

public class InsertSort implements IArraySort {

    @Override 
    public  int [] sort( int [] sourceArray) throws Exception {
         // Copy arr without changing the parameter content 
        int [] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // Select the appropriate position to insert from the element with subscript 1, because there is only one element with subscript 0, the default is ordered 
        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 and find a smaller number 
            int j = i;
             while (j > 0 && tmp < arr[j - 1 ]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // there is a smaller number, insert 
            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;
        }
}

Swift instance

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)
        }
    }
}

Leave a Comment

Your email address will not be published. Required fields are marked *