C++ Insertion Sort Algorithm Implementation and Explanation

The given code is an implementation of the Insertion Sort algorithm in C++.

'void Insert_sort(int data[],size_t size) { for (int i = 1; i < size; i++) { int temp = data[i]; //存放第i个数 for (int j = i-1; j >=0; j--) { if(data[j]>temp) data[j+1]=data[j]; } data[j+1]=temp; }

}'

The 'Insert_sort' function takes an array of integers and its size as input parameters. It sorts the array in ascending order using the Insertion Sort algorithm.

Here is a step-by-step explanation of how the algorithm works:

1. The outer loop iterates over each element in the array, starting from the second element (i = 1).
2. Inside the outer loop, a variable named 'temp' is used to store the value of the current element ('data[i]').
3. The inner loop starts from the previous element (j = i-1) and continues until it reaches the beginning of the array (j >= 0).
4. Inside the inner loop, if the value at 'data[j]' is greater than the value in 'temp', it means that we need to shift the elements to the right to make space for the current element.
5. So, the value at 'data[j]' is moved to the next position ('data[j+1]').
6. The inner loop continues until either the value at 'data[j]' is smaller than or equal to 'temp' or j reaches the beginning of the array.
7. After the inner loop ends, we have found the correct position for the current element, and 'temp' is placed at that position ('data[j+1] = temp').
8. The outer loop continues until all elements in the array have been processed.
9. Once the outer loop ends, the array is sorted in ascending order.

Overall, the Insertion Sort algorithm has a time complexity of O(n^2) in the worst case, where n is the number of elements in the array. It is an efficient sorting algorithm for small-sized arrays or partially sorted arrays.