Posted by : Nguyễn Văn Tuấn 30 March 2014

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Thuật toán:
Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a_1,...,a_{k}. Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a_1,...,a_{k-1} đã được sắp. Để sắp xếp phần tử a_k=x ta tìm vị trí thích hợp của nó trong dãy a_1,...,a_{k-1}. Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x Vị trí thích hợp Các phần tử>x Các phần tử chưa sắp
a_1 ... a_{i-1} x a_{i+1} ... a_{k-1} a_{k+1} ... a_n



Code:

#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
     int i,tg,x;
     for (i=1;i<n;i++)
      {
        tg=a[i];
        x=i-1;
        while((x>=0)&&(a[x]>tg))
            {
            a[x+1] = a[x];
            x--;
            }
        a[x+1] =tg;
     }
}

int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    insertion_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}






Leave a Reply

Subscribe to Posts | Subscribe to Comments

- Copyright © Kiến thức tổng quan - Kiến Thức Tổng Quan - Powered by Blogger - Designed by SnowBlack -