Code C/C++: Thuật toán sắp xếp chèn (Insertion Sort)

Ý tưởng thuật toán: xét dãy n phần tử a0, a1, …,an-1
- Xem dãy gồm 1 phần tử là a0 dãy có thứ tự.
- Thêm a1 vào dãy có thứ tự a0 sao cho dãy mới a0, a1 là dãy có thứ tự. Nếu a1 < a0  ta hoán vị avới a0.
- Thêm a2  vào dãy có thứ tự a0, a1 sao cho dãy mới a0, a1, a2 là dãy có thứ tự.
- Tiếp tục như thế đến n-1 bước ta sẽ có dãy có thứ tự a0, a1, …,an-1
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.
Cài đặt thuật toán:
#include <iostream>
#include <conio.h>
#define max 100
using namespace std;
//Nhập mảng
void NhapMang(int A[],int n)  {
for(int i=0; i<n;  i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
//Xuất mảng
void XuatMang(int A[],int n){
cout<<endl;
for(int i=0; i<n;  i++)
cout<<A[i]<<"\t";
}
//Hoán vị 2 phần tử
void Swap(int &a,int &b)  {
int temp = a;
a = b;
b =  temp; 
}
//Thủ tục 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]);
}
//Chương trình chính
int main() {
int A[max],n;
cout<<"Nhap so phan tu:";
cin>>n;
NhapMang(A,n);
cout<<"\nMang vua nhap la:";
XuatMang(A,n);
cout<<endl;
InsertionSort (A,n);
cout<<"\nMang vua sap xep la:";
XuatMang(A,n);
getch();
return 0;
}
Kết quả chạy chương trình:
Từ khóa: Sắp xếp, thuật toán, chèn, insert, insertion sort, sắp xếp chèn, giải thuật, cấu trúc dữ liệu và giải thuật

Related Posts
Previous
« Prev Post

2 comments

June 12, 2016 at 10:49 AM

@@~ giống hệt thuật toán nổi bọt ạ?

Reply
avatar
June 5, 2017 at 9:52 PM

Ad có thể giúp mình cái thuật toán Bin Sort được không! mình tìm trên mạng hoài mà không được!

Reply
avatar