[ 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.

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();