Ý tưởng Giải thuật và Code tham khảo phương pháp xếp chọn(selection sort )
Ý tưởng của giải thuật xếp chọn( Selection sort)
Với mảng gồm n phần tử (Ai,Ai+1,…,An-1). Trước hết ta xét với n phần tử đầu tiên và chọn ra phần tử nhỏ nhất trong n phần tử đó và đưa phần tử này về vị trí đúng của nó là vị trí đầu tiên của dãy hiện hành. Sau đó chúng ta không quan tâm đến phần tử đó nữa, xem dãy hiện hành bây giờ chỉ còn n-1 phần tử của dãy ban đầu, và bắt đầu với vị trí thứ 2, tiếp tục lặp lại quá trình trên cho dãy hiện hành. Cứ như vậy đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng của giải thuật là thực hiện n-1 lượt đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy :
Tiến hành :
Mô tả thuật giải:
B1: Với i=0;
B2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1].
B3: Hoán vị đổi chỗ vị trí a[min] với a[i].
B4: Nếu i
Ngược lại : Dừng // n-1 đã đc sắp xếp đúng vị trí
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void SelectionSort(float a[], int n)
{
int min; //chi so phan tu nho nhat cua day hien hanh
for (int i = 0; i < n-1; i++)
{
min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j; // xác nhân. vi tri phan tu nho nhât
if (a[min]<a[i])
{
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
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 Selection Sort:"<<endl;
cout<<endl;
SelectionSort(a,n);
output(a,n);
}
}
0 Response to "Ý tưởng Giải thuật và Code tham khảo phương pháp xếp chọn(selection sort )"
Đăng nhận xét