Thuật toán sắp xếp chèn – Insertion Sort code C++

Thuật toán sắp xếp chèn là gì? Cài đặt thuật toán Insertion sort bằng ngôn ngữ C++ là nội dung mình muốn chia sẻ cho bạn trong bài viết này.

1. Sắp xếp chèn là gì?

Sắp xếp chèn ( Insertion Sort) là một thuật toán sắp xếp khá nhanh và tối ưu. Về lý thuyết của nó bạn có thể xem tại Wikipedia.
Độ phức tạp của thuật toán: n^2

Nội dung của thuật toán đó chính là khi duyệt mảng, bạn tìm vị trí phù hợp để chèn phần tử đang duyệt sao cho danh sách từ vị trí đầu đến vị trí phần tử đang xét đó vẫn tăng (hoặc giảm).

Giả sử bạn cần sắp xếp mảng a[n] ( mảng có n phần tử). Chúng ta sẽ bắt đầu duyệt mảng từ vị trí i=1 tới i<n ( bỏ qua i =0). Tại vị trí i=k, bạn cần tìm vị trí cho a[k] phù hợp trong đoạn từ i=0 đến k để chèn a[k] vào thỏa mãn mảng tăng ( giảm).

2. Giải thuật InsertSort code C++

Để thực hiện ý tưởng bên trên, với mỗi a[i], mình sẽ tìm vị trí cho nó. a[k] chính là biến temp.
Trong khi vị trí chưa phù hợp ( while j>=0 && temp ), thì dịch vị trí phần tử trước nó lên một đơn vị ( a[i+j]=a[j] )
Tiếp tục giảm biến j;

Dưới đây là phần code của mình, bạn có thể

// InsertSort Algorithms by duongdinh24
#include <iostream>
using namespace std;

// InsertSort function
void InsertSort(int a[],int n){
    int temp, j;
    for(int i=1;i<n;i++){
        j=i-1;
        temp=a[i];
        while(j>=0 && temp<a[j]){  // cho toi khi chua tim duoc vi tri phu hop

            a[j+1]=a[j];  // Gan dich bien a[j] len mot don vi

            j--;  // Giam dan j = 0 de tim vi tri phu hop cho tempt
        }
        a[j+1]=temp;  // chen vao vi tri can chen
    }
}


// This function call InsertSort function

void Input(int a[], int n){
    cout<<"Nhap mang: "<<endl;
    for(int i=0;i<n;i++)
        cin>>a[i];

    InsertSort(a,n);   // call function InsertSort
    cout<<"Array after Sort: "<<endl;

    for(int i=0;i<n;i++)
        cout<<a[i]<<"\t";
}

int main(){
    int a[10];
    Input(a,10);
    printf("\nDone!");
    return 0;
}

Đoạn bên trên là demo của thuật toán sắp xếp chèn viết bằng ngôn ngữ C++. Kết quả khi chạy chương trình trên:

Cảm ơn bạn đã quan tâm bài viết. Nếu có vướng mắc gì, để lại comment dưới bài viết này nhé!

Đừng bỏ lỡ các thuật toán sắp xếp khác trên blog của mình nhé!