Ý tưởng và Code tham khảo của giải thuật xếp chèn( Insertion sort)
Ý tưởng của giải thuật xếp chèn( Insertion sort)
Giả sử mảng gồm n phần tử (A0,A1,A2,…,An-1) trong đó i phần tử đầu tiên A0,A1,…,Ai-1 đã có thứ tự. Ý tưởng chính của phương pháp chèn trực tiếp là tìm cách chèn phần tử Ai vào vị trí thích hợp của đoạn đã đc sắp xếp để có dãy mới A0,A1,…,Ai có thứ tự !
Vị trí chèn có thể là :
+ Trước A0
+ Sau Ai-1
+ Giữa 2 phần tử Ak-1 và Ak thỏa Ak-1<=Ai<=Ak ( 1<=k<=i-1)
Cho dãy ban đầu A0,A1,A2,…,An-1 ta có thể xem như đã có đoạn gồm 1 phần tử A0 đã đc sắp.
Sau đó, thêm A1 vào đoạn A0 --> ta có đoạn A0,A1 đc sắp.
Tiếp tục, ta thêm vào đoạn A0,A1 phần tử A2 --> ta có đoạn A0,A1,A2 đc sắp
………
Tiếp tục như vậy cho đến khi thêm xong An-1 vào đoan A0,A1,…,An-2 --> ta có đoạn A0,A1,…,An-1 đc sắp .
Tiến hành :
Mô tả thuật giải:
B1: Với i=1; // đoạn có 1 phần tử A[0] đã đc sắp
B2: x=A[i]// Tìm vị trí (vt) thích hợp trong đoạn A[0] đến A[i-1] để chèn x vào
// đồng thời gán x=A[i] giúp lưu giá trị A[i] tránh bị ghi đè khi dời chỗ các phần tử
B3: Dời các phần tử A[vt] đến A[i-1] sang phải 1 vị trí để dành chỗ cho A[i]
B4: A[vt]=x; // có đoạn A[0],A[1],…,A[i] đã đc sắp
B5: Tăng i=i+1;
Nếu i<n-1--> lặp lại B2.
Ngược lại -->dừng
Các bạn tham khảo code :
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void InsertionSort(float a[],int n)
{
float x;
for(int i=1;i<n;i++)
{
x=a[i];// luu giá tri a[i] tránh bi ghi dè khi doi cho các ptu
int vt=i-1;//tiên' vê ` trai' tìm vi tri chen x
while ((a[vt]>x)&&(vt>=0))
{
a[vt+1]=a[vt];
vt--;
}
a[vt+1]=x;// chèn x vào dãy
}
}
void input(float a[],int n)
{
int i;
for (i = 0; i <n; i++)
{
cout<<"a["<<i<<"]= ";
cin>>a[i];
}
}
void output(float a[],int n)
{
int i;
for (i = 0; i <n; i++)
cout<<a[i]<<" ";
}
void main()
{
cout<<"Nhap n : ";cin>>n;
if(n>0)
{
cout<<"Day ban dau: ";
input(a,n);
cout<<endl;
cout<<"\nSap xep theo PP insertion sort:"<<endl;
cout<<endl;
InsertionSort(a,n);
output(a,n);
}
getch();
}
0 Response to "Ý tưởng và Code tham khảo của giải thuật xếp chèn( Insertion sort)"
Đăng nhận xét