Ý tưởng và Code tham khảo của giải thuật sắp xếp nổi bọt ( Bubble sort)
Ý tưởng của giải thuật sắp xếp nổi bọt ( Bubble sort)
Ý tưởng chính của thuật giải là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành.
Sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ I sẽ có vị trí đầu dãy là i . Lặp lại xử lý cho đến khi không còn cặp phần tử nào để xét .
Mô tả thuật giải :
Tiến hành :
B1: i=0; // lần xử lý đầu tiên
B2: j= n-1; // duyệt từ cuối dãy về vị trí i
Trong khi (j<i) thì thực hiện:
Nếu a[j]<a[j-1] // a[j], a[j-1] xét cặp phần tử kế cận
j=j-1;
Hoán vị đổi chỗ vị trí a[j] với a[j-1]
B3: i=i+1; // lần xử lý kế tiếp
Nếu i= n-1: Hết dãy …dừng
Ngược lại : lặp lại B2
Các ban tham khảo Code :
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void BubbleSort(float a[],int n)
{
int temp;
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(a[j]<a[j-1])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
void input(float a[],int n)
{
int i;
for (i = 1; i <= n; i++)
{
cout<<"a["<<i<<"]= ";
cin>>a[i];
}
}
void output(float a[],int n)
{
int i;
for (i = 1; 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 Bubble sort:"<<endl;
cout<<endl;
BubbleSort(a,n);
output(a,n);
}
getch();
}
0 Response to "Ý tưởng và Code tham khảo của giải thuật sắp xếp nổi bọt ( Bubble sort)"
Đăng nhận xét