[Thuật toán] Các thuật toán sắp xếp trong lập trình C- Thuật toán sắp xếp chèn

Share:



  • Bubble sort. (Nổi bọt, nổi bong bóng)
  • Quick sort. (Sắp xếp nhanh)
  • Simple selection sort. (Sắp xếp chọn)

  • 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=xta 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ử ≤xVị trí thích hợpCác phần tử>xCác phần tử chưa sắp
    a_1...a_{i-1}xa_{i+1}...a_{k-1}a_{k+1}...a_n

    Mô tả thuật toán sắp xếp chèn - tinhoccoban.net
    Mô tả thuật toán sắp xếp chèn
    Thuật toán viết bằng C++ : 
    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] << "  ";}

    5.Heap sort. (Sắp xếp vun đống)
    6.Simple insertion sort.(Sắp xếp chèn)
    7. Shell sort.
    8.Merge sort. (Sắp xếp hòa nhập)