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();
}
// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác
--------------------------------------------
Xem thêm các thuật toán khác:
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
Chúc các bạn thành công!
