C++ insert sort algorithm example

Insertion sort

Nothing like to look at the data structure and algorithm, to increase their understanding of the data structure and algorithm, but also increase their programming skills. Insertion sort is one of the most common sorts, and it's easy to understand. Now, for example, the following data needs to be sorted:

10, 3, 8, 0, 6, 9, 2

When using insertion sort for ascending sort, the sort steps are as follows:

10, 3, 8, 0, 6, 9, 2 // take the element 3 and compare it to 10

3, 10, 8, 0, 6, 9, 2 // since 10 is larger than 3, move 10 backwards, and put 3 in the original 10 position; I'm going to take 8 and compare it to the previous element, 10

3, 8, 10, 0, 6, 9, 2 // And then 8 over 3, 8 is greater than 3, so it's not moving anymore; And so on

...

0, 2, 3, 6, 8, 9, 10

That is, every time we take an element, we compare that element to the one that was already sorted.

The worst time complexity of insertion sort is O(n^2). At the same time, the algorithm does not need to open up additional space, are in the original space to move operations.

Code implementation

#include <iostream>

using namespace std;

 

void InsertSort(int arr[], int length)

{

     int temp;

     for (int i = 1; i < length; ++i) //Start with the second element in the array 

     {

          temp = arr[i]; //Record the current element 

          int j = i - 1;

          while (j >= 0 && temp < arr[j]) //Compares the current element with the previous sorted sequence elements one by one 

          {

               arr[j + 1] = arr[j]; //The sorted sequence moves back 
 as a whole
               --j;

          }

          arr[j + 1] = temp; //Insert the current element 

     }

}

 

int main()

{

     int arr[10] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5};

 

     InsertSort(arr, 10);

 

     for (int i = 0; i < 10; ++i)

     {

          cout<<arr[i]<<" ";

     }

     cout<<endl;

 

     return 0;

}