Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thuật toán Selection Sort

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Thuật toán Selection Sort

Bài gửi  admin on Sat Apr 17, 2010 8:56 am

Ý 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();
}

    Hôm nay: Tue Jun 19, 2018 9:22 pm