[ Sort ] Thuật toán Insert-Sort [Code C++]

 Thuật toán Insert-Sort


Ý tưởng thuật toán: xét dãy n phần tử a[0], a[1], a[2] ,..., a[n-1].
- Xem dãy gồm 1 phần tử a[0] là dãy có thứ tự.
- Thêm a[1] vào dãy có thứ tự a[0] sao cho dãy mới a[0], a[1] là dãy có thứ tự. Nếu a[1] < a[0] ta đổi chỗ a[1] với a[0].
- Thêm a[2] vào dãy có thứ tự a[0], a[1] sao cho dãy mới a[0], a[1], a[2] là dãy có thứ tự.
- Tương tự, tiếp tục như thế đến n – 1 bước ta sẽ có dãy có thứ tự.

Ví dụ: sử dụng thuật toán Insertion Sort sắp xếp dãy {3,7,22,3,1,5,8,4,3,9} theo thứ tự tăng dần.

Thuật toán Insert-Sort

Kết quả sau khi đã thực hiện thuật toán: {1,3,3,3,4,5,7,9,22}

Cài đặt thuật toán:

[Code Turbo C++]

#include <iostream.h>
#include <conio.h>
#define max 100
//nhap day
void NhapDay(int a[],int n) {
   for(int i=0; i<n; i++) {
    cout<<"\n a["<<i<<"] =";
    cin>>a[i];
   }
}
//xuat day
void XuatDay(int a[],int n) {
   cout<<"\n IN DAY: ";
   for(int i=0; i<n; i++)
     cout<<a[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
   int t = a;
   a = b;
   b = t;
}
//thu tuc Insertion Sort
void InsertionSort(int a[],int n) {
   for(int i=1; i<n; i++)
     for(int j=i; j>0; j--)
       if(a[j]<a[j-1])
        Swap(a[j],a[j-1]);
}
//chuong trinh chinh
void main() {
  int a[max],n;
  clrscr();
  cout<<"Nhap so phan tu:";
  cin>>n;
  NhapDay(a,n);
  cout<<"\n Day vua nhap la:";
  XuatDay(a,n);
  cout<<endl;
  InsertionSort (a,n);
  cout<<"\n Day vua sap xep la:";
  XuatDay(a,n);
  getch();
}

// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác

Tìm kiếm nội dung khác: