Insert sort directly

This chapter introduces the direct insertion sorting in the sorting algorithm . The content includes ：
1.  Introduction to direct insertion sorting
2.  Insert the sorting text description directly
3.  The time complexity and stability of direct insertion sorting
4.  Direct insertion sort implementation
4.1   Direct insert sort C Realization
4.2   Direct insert sort C++ Realization
4.3   Direct insert sort Java Realization

Reprint please indicate the source ： Direct insert sort - If the sky doesn't die - Blog Garden

---

More ： Data structure and algorithm series Catalog

Introduction to direct insertion sorting

Direct insert sort (Straight Insertion Sort) The basic idea of ： hold n The elements to be sorted look like an ordered table and an unordered table . At the beginning, the ordered table contains only 1 Elements , The unordered table contains n-1 Elements , The first element is taken out of the unordered table every time during sorting , Insert it in place in an ordered table , Make it a new ordered table , repeat n-1 The sorting process can be completed .

Insert the sorting text description directly

Insert sort code directly

/*
 *  Direct insert sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void insert_sort(int a[], int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        // by a[i] In front of a[0...i-1] Find a suitable position in the ordered interval 
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        // If you find a suitable position 
        if (j != i - 1)
        {
            // Will compare a[i] Big data moves backward 
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            // take a[i] Put it in the right place 
            a[k + 1] = temp;
        }
    }
}

Next, select an intermediate process of direct insertion sorting to explain it . hypothesis {20,30,40,10,60,50} In front of 3 The number has been arranged , It's ordered ; And then to 10 Arrange . The schematic diagram is as follows ：

In the graph, the sequence is divided into ordered region and disordered region . There are only two things we need to do ：(1) Take out the... In the disordered area 1 Number , And find its corresponding position in the ordered region .(2) Insert the data of the unordered area into the ordered area ; If necessary , Then shift the relevant data in the ordered area .

The time complexity and stability of direct insertion sorting

Direct insertion sort time complexity
The time complexity of direct insertion sorting is O(N2).
Let's assume that the sequence being sorted has N Number . The time complexity of traversing a trip is O(N), How many times does it take to traverse ？N-1！ therefore , The time complexity of direct insertion sorting is O(N2).

Direct insert sort stability
Direct insertion sorting is a stable algorithm , It satisfies the definition of stable algorithm .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable ！

Direct insertion sort implementation

Direct insert sort C Realization
Implementation code (insert_sort.c)

/**
 *  Direct insert sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <stdio.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )

/*
 *  Direct insert sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void insert_sort(int a[], int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        // by a[i] In front of a[0...i-1] Find a suitable position in the ordered interval 
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        // If you find a suitable position 
        if (j != i - 1)
        {
            // Will compare a[i] Big data moves backward 
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            // take a[i] Put it in the right place 
            a[k + 1] = temp;
        }
    }
}

void main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    insert_sort(a, ilen);

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Direct insert sort C++ Realization
Implementation code (InsertSort.cpp)

/**
 *  Direct insert sort ：C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 *  Direct insert sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void insertSort(int* a, int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        // by a[i] In front of a[0...i-1] Find a suitable position in the ordered interval 
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        // If you find a suitable position 
        if (j != i - 1)
        {
            // Will compare a[i] Big data moves backward 
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            // take a[i] Put it in the right place 
            a[k + 1] = temp;
        }
    }
}

int main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    insertSort(a, ilen);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Direct insert sort Java Realization
Implementation code (InsertSort.java)

/**
 *  Direct insert sort ：Java
 *
 * @author skywang
 * @date 2014/03/11
 */

public class InsertSort {

    /*
     *  Direct insert sort 
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     n --  Length of array 
     */
    public static void insertSort(int[] a, int n) {
        int i, j, k;

        for (i = 1; i < n; i++) {

            // by a[i] In front of a[0...i-1] Find a suitable position in the ordered interval 
            for (j = i - 1; j >= 0; j--)
                if (a[j] < a[i])
                    break;

            // If you find a suitable position 
            if (j != i - 1) {
                // Will compare a[i] Big data moves backward 
                int temp = a[i];
                for (k = i - 1; k > j; k--)
                    a[k + 1] = a[k];
                // take a[i] Put it in the right place 
                a[k + 1] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {20,40,30,10,60,50};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        insertSort(a, a.length);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

above 3 The principle and output of the two implementations are the same . Here is their output ：

before sort:20 40 30 10 60 50 
after  sort:10 20 30 40 50 60