Thuật toán Selection-Sort
Ý tưởng thuật toán: xét dãy n phần tử a[0], a[1], a[2] ,..., a[n-1].
- Chọn trong dãy a[1], a[1], a[2] ,..., a[n-1] ra phần tử có khỏa nhỏ nhất và đổi chỗ nó với a[1].
- Tương tự, 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}.
[Mô phỏng]
Kết quả 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:
[Code Turbo C++]
#include <iostream.h>// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác
#include <conio.h>
#define max 100
//nhap day
void NhapDay(int a[],int n) {
for(int i=0; i<n; i++) {
cout<<"\n a["<<i<<"] =";
cin>>a[i];
}
}
//xuat day
void XuatDay(int a[],int n) {
cout<<"\n IN DAY: ";
for(int i=0; i<n; i++)
cout<<a[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
int t = a;
a = b;
b = t;
}
//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]); // doi chu 2 phan tu
}
}
//chuong trinh chinh
void main() {
int a[max],n;
clrscr();
cout<<"Nhap so phan tu:";
cin>>n;
NhapDay(a,n);
cout<<"\n Day vua nhap la:";
XuatDay(a,n);
cout<<endl;
SelectionSort (a,n);
cout<<"\n Day vua sap xep la:";
XuatDay(a,n);
getch();
}
--------------------------------------------
Xem thêm các thuật toán khác:
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*
Chúc các bạn thành công!