Insertion sorting algorithm

алгоритм, сортировка, Sort Algorithm

This description is intended to help you understand what the insertion sort algorithm is and how to implement it in programming.

Technical details, properties, and comparison with other sorting algorithms are out of the question here. If you know what the insertion sort algorithm is, visit this page for insertion sort properties and comparisons with other sorting algorithms.

How does the insertion sort algorithm work?

Algorithm explanations:


Suppose you want to sort the elements in ascending order as shown in the image above. Then the following steps are performed:

• Step 1: The second element of the array is compared with the elements that appear before it (in this case, only the first element). If the second element is less than the first element, the second element is inserted at the position of the first element. After the first step, the first two elements of the array will be sorted.
• Step 2: The third element of the array is compared with the elements that appear before it (the first and second element). If the third element is less than the first, it is inserted at the position of the first element. If the third element is greater than the first element but less than the second element, it is inserted at the position of the second element. If the third element is greater than both elements, it stays in the same position. After the second step, the first three elements of the array will be sorted.
• Step 3: Similarly, the fourth element of the array is compared with the elements that appear before it (first, second and third element) and the same procedure is applied and this element is inserted in the correct position. After the third step, the first four elements of the array will be sorted.

If there are n elements to sort, then this procedure is repeated n-1 times to get a sorted array list.

Sort elements of a C program using the insert sorting algorithm

/*Сортировка элементов массива в порядке возрастания с использованием алгоритма сортировки вставками*/
#include<stdio.h>
int main()
{
    int data[100],n,temp,i,j;
    printf("Enter number of terms(should be less than 100): ");
    scanf("%d",&n);
    printf("Enter elements: ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&data[i]);
    }
    for(i=1;i<n;i++)
    {
        temp = data[i];
        j=i-1;
        while(temp<data[j] && j>=0)
/*Чтобы отсортировать элементы в порядке убывания, измените temp <data [j] на temp> data [j] в строке выше.*/
        {
            data[j+1] = data[j];
            --j;
        }
        data[j+1]=temp;
    }
    printf("In ascending order: ");
    for(i=0; i<n; i++)
        printf("%d\t",data[i]);
    return 0;
}

Note: Although this program is written in C, the insertion sort algorithm can be used similarly in other programming languages.

Output on display:

Enter number of terms(should be less than 100): 5
Enter elements: 12
1
2
5
3
In ascending order: 1     2     3     5     12

Here is another source code that uses the same insertion sort algorithm technique to sort the elements of an array.

/ * Этот исходный код также является реализацией алгоритма сортировки вставками для сортировки элементов массива. * /
/ * Эта программа немного сложна, поскольку содержит несколько циклов. * /
/ * Программа для сортировки массива в порядке убывания * /
#include <stdio.h>
int main()
{
    int data[100],n,i,j,hold,k;
    printf("Enter number of terms(should be less than 100): ");
    scanf("%d",&n);
    printf("Enter elements: ");
    for(i=0;i<=n-1;++i)
    {
       scanf("%d",&data[i]);
    }
    for(i=1;i<=n-1;++i)
    {
    for(j=0;j<i;++j)
       if(data[j]<data[i])
/ * Чтобы отсортировать элементы в порядке возрастания, измените <на> в строке выше. * /
       {
           hold=data[i];
           k=i;
           while(k!=j)
           {
               data[k]=data[k-1];
               --k;
           }
           data[j]=hold;
       }
    }
    printf("In descending Order: ");
    for(i=0;i<=n-1;++i)
     {
       printf("%d    ",data[i]);
    }
    return 0;
}