Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.
Thuật toán:
Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu
. Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu
đã được sắp. Để sắp xếp phần tử
ta tìm vị trí thích hợp của nó trong dãy
. Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.
Thuật toán:
Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu
Các phần tử ≤x | Vị trí thích hợp | Các phần tử>x | Các phần tử chưa sắp | ||||||
... | x | ... | ... |
![]() |
Mô tả thuật toán sắp xếp chèn |
Code:
#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
int i,tg,x;
for (i=1;i<n;i++)
{
tg=a[i];
x=i-1;
while((x>=0)&&(a[x]>tg))
{
a[x+1] = a[x];
x--;
}
a[x+1] =tg;
}
}
int main()
{
int n;
cout <<"Nhap so cac so hang can sap xep: ";
cin >> n;
int a[n];
cout<<"Nhap cac so hang: "<<endl;
for(int i=0;i<n;i++)
{
cout<<"a"<<i+1<<": " ;
cin >>a[i];
cout << endl;
}
insertion_sort(a,n);
cout<<"Day sau khi sap xep: ";
for(int i=0;i<n;i++)
cout<<a[i] << " ";}
#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
int i,tg,x;
for (i=1;i<n;i++)
{
tg=a[i];
x=i-1;
while((x>=0)&&(a[x]>tg))
{
a[x+1] = a[x];
x--;
}
a[x+1] =tg;
}
}
int main()
{
int n;
cout <<"Nhap so cac so hang can sap xep: ";
cin >> n;
int a[n];
cout<<"Nhap cac so hang: "<<endl;
for(int i=0;i<n;i++)
{
cout<<"a"<<i+1<<": " ;
cin >>a[i];
cout << endl;
}
insertion_sort(a,n);
cout<<"Day sau khi sap xep: ";
for(int i=0;i<n;i++)
cout<<a[i] << " ";}