How to use insertion sort algorithm in C++

Use the insertion sort algorithm in C to implement array sorting

Insertion sort is a simple but effective sorting algorithm that inserts the elements to be sorted one by one The sorted list results in an ordered list. This article will introduce how to use the C programming language to implement the insertion sort algorithm and give specific code examples.

Algorithm idea:
The basic idea of ​​insertion sort is to divide the array into sorted intervals and unsorted intervals. Each time an element is selected from the unsorted range and inserted into the appropriate position of the sorted range until the unsorted range is empty.

Specific steps:

1. Traverse the array and insert the elements of the unsorted interval into the sorted interval in sequence.
2. For each element in the unsorted interval, compare it with the elements in the sorted interval in order to find the insertion position.
3. Insert the element into the appropriate position of the sorted interval, and move the elements of the sorted interval one position backward.

Code example:
The following is a sample code that uses the C programming language to implement the insertion sort algorithm:

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = { 5, 2, 4, 6, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "原始数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    insertionSort(arr, n);

    std::cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

In the above code, we define a method named insertionSort function to implement insertion sort. In the main function, we define an array to be sorted and call the insertionSort function to sort it. Finally, we output the sorted results to the console.

Running results:
Original array: 5 2 4 6 1 3
Sorted array: 1 2 3 4 5 6

Summary:
Through the above example code , we can see how to sort an array using the insertion sort algorithm in C. Although insertion sort is simple, its time complexity is O(n^2), and its sorting efficiency for large-scale data is low. In practical applications, if a large amount of data needs to be sorted, it is recommended to use a more efficient sorting algorithm, such as quick sort or merge sort.

The above is the detailed content of How to use insertion sort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!