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ử a_0, a_{1, …,}a_n-1
- Xem dãy gồm 1 phần tử là a₀ dãy có thứ tự.

- Thêm a₁ vào dãy có thứ tự a₀ sao cho dãy mới a_0, a₁ là dãy có thứ tự. Nếu a_{1 <} a₀  ta hoán vị a₁ với a_0.

- Thêm a₂  vào dãy có thứ tự a_0, a₁ sao cho dãy mới a_0, a_1, a₂ 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ự a_0, a_{1, …,}a_n-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