Ý tưởng thuật toán: xét dãy n phần tử a_0,a_1...a_(n-1)
- Chọn trong dãy a_0,a_1...a_(n-1) ra phần tử có khỏa nhỏ nhất và hoán vị nó với a_0.
Chọn trong dãy a_1,a_2...a_(n-1) ra phần tử có khỏa nhỏ nhất và hoán vị nó với a_1.
Cứ tiếp tục như thế sau n – 1 bước ta thu được danh sách có thứ tự.
Code:
#include <iostream.h>
#include <conio.h>
#define max 100
//nhap mang
void NhapMang(int A[],int n) {
for(int i=0; i<n; i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
//xuat mang
void XuatMang(int A[],int n) {
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
//thuat toan Selection Sort
void SelectionSort(int A[],int n) {
int min; // chi so phan tu nho nhat trong day hien hanh
for(int i=0; i<n-1; i++) {
min = i;
for(int j=i+1; j<n; j++)
if(A[min]>A[j])
min = j; //ghi nhan vi tri phan tu nho nhat
if(min != i)
Swap(A[i],A[min]);
}
}
//chuong trinh chinh
void main() {
int A[max],n;
clrscr();
cout<<"Nhap so phan tu:";
cin>>n;
NhapMang(A,n);
cout<<"\nMang vua nhap la:";
XuatMang(A,n);
cout<<endl;
SelectionSort (A,n);
cout<<"\nMang vua sap xep la:";
XuatMang(A,n);
getch();
}