Code C/C++: Thuật toán sắp xếp lựa chọn (Selection Sort)

Ý 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₀.
- 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₁.
- Cứ tiếp tục như thế sau n –1 bước ta thu được danh sách có thứ tự.
Ví dụ:

Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 4, 5, 6, 6, 7, 7, 8, 9}.
Cài đặt thuật toán:
#include <iostream>
#include <conio.h>
#define max 100
using namespace std;
//Nhập mảng
void NhapMang(int A[],int n) {
for(int i=0; i<n;  i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
//Xuất mảng
void XuatMang(int A[],int n){
cout<<endl;
for(int i=0; i<n;  i++)
cout<<A[i]<<"\t";
}
//Hoán vị 2 phần tử
void Swap(int &a,int &b){
int temp = a;
a = b;
b =  temp;
}
//Thuật toán Selection Sort
void SelectionSort(int A[],int n) {
int min;        
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]);
}
}
//Chương trình chính
int main() {
int A[max],n;
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();
return 0;

}
Kết quả chạy chương trình:

Tag: Sắp xếp,Bubble sort, thuật toán, sắp xếp lựa chọn, Selection Sort