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ử a0, a1, …,an-1
- Chọn trong dãy a0, a1, …,an-1 ra phần tử có khóa nhỏ nhất và hoán vị nó với a0.
- Chọn trong dãy a1, a2, …,an-1 ra phần tử có khóa nhỏ nhất và hoán vị nó với a1.
- 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

Related Posts
Previous
« Prev Post

3 comments

March 1, 2016 at 3:06 PM

câu getch() em thay bằng system("pause") n mới chạy :'<

Reply
avatar
March 2, 2016 at 5:36 AM

Chào Tú Anh Nguyễn
Nếu bạn sử dụng dev C++ để viết thì không cần sử dụng getch(). Hoặc có thể thêm system("pause") cũng được.
Cảm ơn bạn

Reply
avatar