[Phần 3] Thuật toán sắp xếp chèn (insert sort)

1. Tư tưởng của thuật toán sắp xếp chèn. (insert sort)

Tư tưởng của thuật toán này giống như bạn chơi bài, lúc cầm 13 quân bài lên, bạn sẽ tìm cách để chèn các lá bài vào chỗ hợp lý của nó.

Giả định có n phần tử, từ a[1]->a[n] và muốn sắp xếp tăng dần.

Đầu tiên, coi như chỉ có a[1], thì a[1] đã được sắp xếp.
Bây giờ tiếp theo xét dãy: a[1] và a[2], thì ta lấy a[2] chèn vào vị trí hợp lý sao cho dãy tăng dần.
Tiếp tục, xét dãy: a[1], a[2] và a[3], thì lại lấy tiếp a[3] chèn vào các vị trí nào đó sao cho dãy tăng dần.
Cứ như thế, đến cuối cùng thì xét dãy: a[1], a[2], a[3] … … … … a[n]. Lấy ra a[n] rồi chèn vào chỗ thích hợp sao cho dãy tăng dần.

2. Mô tả thuật toán bằng ngôn ngữ C++.


//hanhtrinhtuoitre.com
//[Phần 3] Thuật toán sắp xếp chèn (insert sort)
#include <iostream>
using namespace std;

void NhapMang (int A[], int n){
    for(int i = 0; i < n; i++)
    {
        cout<<"Nhap phan tu thu A["<< i <<"] =";
        cin>>A[i];
    }
}

void XuatMang (int A[], int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << A[i]<< "  ";
    }
}

void HoanVi (int &a, int &b)
{
    //cho nay truyen tham chieu: (int &a, int &b)
    //Khong phai la truyen tham tri: (int a, int b)
    int temp = a;
    a = b;
    b = temp;
}

void BubbleSort(int A[], int n){
    for(int i = 1; i <n; i++){
        for(int j = i; j>0; j--){
            if(A[j]< A[j-1]){
                HoanVi(A[j], A[j-1]);
              
            }else {
                break;
            }
        }
    }
}

int main() {
    int A[100], n;
    cout<<"Nhap so phan tu:";
    cin>>n;
    NhapMang (A,n);
    cout<<"Mang vua nhap la: \n";  // \n tuc la xuong dong
    XuatMang (A,n);
    cout<<endl; // xuong dong
    BubbleSort (A,n);
    cout<<"Mang vua sap xep la: \n"; //  \n tuc la xuong dong
    XuatMang (A,n);
    return 0;
    
}

Nếu bạn muốn chạy trực tiếp các dòng lệnh để thử nghiệm tính chính xác thì có thể trùy cập vào đường link này: http://cpp.sh/8xtr

3. Ví dụ minh họa

This entry was posted in Kinh nghiệm - thủ thuật - tài liệu. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

:1: :2: :12: :46: :59: :51: :38: :31: :22: :15: :8: more »