Chương trình C++ triển khai thuật toán Insertion Sort (Sắp xếp chèn)

Kỹ thuật sắp xếp này tương tự như kỹ thuật sắp xếp bài, nói cách khác chúng ta sắp xếp bài bằng cơ chế sắp xếp chèn. Đối với kỹ thuật này, chúng ta chọn một phần tử từ tập dữ liệu và dịch chuyển các phần tử dữ liệu để tạo chỗ chèn lại phần tử được chọn vào tập dữ liệu.

Độ phức tạp của kỹ thuật Insertion Sort

• Độ phức tạp thời gian: O(n) cho trường hợp tốt nhất, O(n²) cho trường hợp trung bình và xấu nhất
• Độ phức tạp không gian: O(1)

Đầu vào — Danh sách chưa sắp xếp: 9 45 23 71 80 55
Đầu ra — Mảng sau khi sắp xếp: 9 23 45 55 71 80

Thuật toán

insertionSort(array, size)

Đầu vào: Mảng dữ liệu, và tổng số phần tử trong mảng

Đầu ra: Mảng đã sắp xếp

Bắt đầu
    for i := 1 đến size-1
        key := array[i]
        j := i
        while j > 0 VÀ array[j-1] > key
            array[j] := array[j-1]
            j := j – 1
        array[j] := key
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

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

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Mảng trước khi sắp xếp: ";
    display(arr, n);
    insertionSort(arr, n);
    cout << "Mảng sau khi sắp xếp: ";
    display(arr, n);
}

Kết quả đầu ra

Nhập số lượng phần tử: 6
Nhập các phần tử: 9 45 23 71 80 55
Mảng trước khi sắp xếp: 9 45 23 71 80 55
Mảng sau khi sắp xếp: 9 23 45 55 71 80