C + + implementation of direct insertion algorithm

Direct insertion algorithm: insert a keyword to be sorted into the proper position of the ordered sequence according to the size of its value each time until all the keywords to be sorted are inserted into the ordered sequence.

Theoretically, in the direct insertion sort, the second loop can end ahead of time, that is, an element does not cycle to the front of the sequence when it is looking for its proper position.

This is the biggest difference between a direct insert sort and a simple select sort. It is also the reason why direct insertion sorting and simple selection sorting are both time complexity O(n2), but direct insertion sorting is more efficient.

Especially when the data to be sorted is basically in order, this advantage will be extremely obvious. Even at this time, the direct insertion sorting is more efficient than the O(nlogn) sorting algorithm.

#include<iostream>
#include<string>
using namespace std;

template <typename T>
void insertSelectionSort(T arr[],int n){
    //You don't need to consider the 0 th element, because in the initial case of insertion sorting, the 0 th element itself is ordered
    for(int i=1;i<n;i++){
        //Seek arr[i]Suitable insertion position
        //Each comparison is the comparison between the current element and the previous element of the current element, so the judgment condition is j>0 Instead of j>=0
        for(int j=i;j>0&&arr[j-1]>arr[j];j--)
            swap(arr[j],arr[j-1]);
    }
}


int main(){
    int a[10]={10,9,8,7,6,5,4,3,2,1};
    insertSelectionSort(a,10);
    for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;

    float b[3]={3.3f,2.2f,1.1f};
    insertSelectionSort(b,3);
    for(int j=0;j<3;j++)
        cout<<b[j]<<" ";
    cout<<endl;

    string c[4]={"D","C","B","A"};
    insertSelectionSort(c,4);
    for(int k=0;k<4;k++)
        cout<<c[k]<<" ";
    cout<<endl;

    return 0;
}

Output results:

However, if we test the algorithm performance, we will find that the above code does not show this high efficiency advantage.

The reason is that there are a lot of value exchanges in this code, and each value exchange includes three assignments. In this case, it also includes the time to access the location of array index, which is more time-consuming than simple comparison.

So we can optimize the above key code.

 

template <typename T>
void insertSelectionSort(T arr[],int n){

    for(int i=1;i<n;i++){
        //Copy the keywords to be sorted and compare them with the elements in front of them
        T e=arr[i];
        //Need to put j Get the definition of for Outside of the loop, because at the end of the index j The specified location (target location after comparison) inserts the copied keyword e
        int j;    
        for(j=i;j>0&&arr[j-1]>e;j--)
            //Move the keywords larger than the ones to be sorted backward
            arr[j]=arr[j-1];

        arr[j]=e;
    }
}

In this case, instead of calling the swap function to exchange values, we use the assignment statement to complete the corresponding operations.

It greatly optimizes the algorithm.

It should be noted that for direct insertion sorting, a single sorting does not ensure that a keyword reaches its final position.

Tags: C++

Posted on Fri, 03 Apr 2020 16:56:23 -0700 by Beavis2084