Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Sunday, December 7, 2014

Ðây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau:
       • Ðầu tiên chọn phần tử có khóa nhỏ nhất trong n phần tử từ a[1] đến a[n] và hoán vị nó với phần tử a[1].
       • Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ a[2] đến a[n] và hoán vị nó với a[2].
       • Tổng quát ở bước thứ i, chọn phần tử có khoá nhỏ nhất trong n-i+1 phần tử từ   a[i] đến a[n] và hoán vị nó với a[i].
       • Sau n-1 bước này thì mảng đã được sắp xếp.
Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp.


Ví dụ 2-1: Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3
         Bước 1: Ta chọn được phần tử có khoá nhỏ nhất (bằng 2) trong các phần tử từ a[1] đến a[10] là a[3], hoán đổi a[1] và a[3] cho nhau. Sau bước này thì a[1] có khoá nhỏ nhất là 2.
         Bước 2: Ta chọn được phần tử có khoá nhỏ nhất (bằng 2) trong các phần tử từ a[2] đến a[10] là a[4], hoán đổi a[2] và a[4] cho nhau.  Tiếp tục quá trình này và sau 9 bước thì kết thúc. Bảng sau ghi lại các giá trị khoá tương ứng với từng bước.


Code:

Bài Giải



/*
Name: Thuat toan Selection Sort
Copyright: None
Author: Tran Anh
Description: http://www.code.tavn.net
*/
#include<conio.h>
#include<stdio.h>
#include<iostream>
using namespace std;

void swap(int &a, int &b)
{
 int temp;
 temp=a;
 a=b;
 b=temp;
 }

void SelectionSort(int a[], int n)
{
 int jmin;
 for(int i=0;i<n-1;i++)
  {
   jmin=i;
   for(int j=i+1;j<n;j++)
    if (a[jmin]>a[j])
     jmin=j;
   
   if(jmin!=i)
    swap(a[jmin],a[i]);
   }
 }


main()
{
 int n=8;
 int a[]={1,5,3,4,9,7,3,4};

 for(int i=0;i<n;i++)
  cout<<a[i]<<"  ";

  cout<<endl<<"Selection Sort: "<<endl;

 SelectionSort(a,n);

 for(int i=0;i<n;i++)
  cout<<a[i]<<"  ";


 getch();
 return 0;
}


0 comments:

Post a Comment

Popular Posts