Chuyển đến nội dung chính

[ Sort ] Thuật toán Selection-Sort [Code C++]

 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[0], a[1], a[2] ,..., a[n-1] ra phần tử có khỏa nhỏ nhất và đổi chỗ nó với a[0].
 - 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>
#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();
}
// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác



--------------------------------------------
Xem thêm các thuật toán khác: 

BÀI ĐỌC NHIỀU

[Java] Hướng dẫn lập trình Java với NetBean [Clip hướng dẫn]

[Đồ họa trong C\C++] Sử dụng các hàm đồ họa thông dụng trong C\C++ [C\C++]

[ C++ ] Tính đa hình, phương thức ảo, lớp trừu tượng trong C++ [Lập trình hướng đối tượng với C++]

[ Sort ] Thuật toán Heap-Sort [Code C++]

[Algorithm] Thuật toán Đệ quy và một số bài toán Đệ quy cơ bản

[Assembly] Tính tổng 2 số nguyên nhỏ hơn 10 [Lập trình hợp ngữ]

[Assembly] Hướng dẫn sử dụng Emu8086 [Lập trình hợp ngữ]

Bài tập +đáp án Lý thuyết đồ họa máy tính

[Thuật toán đồ thị / code C++] Thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị G

[ C++ ] Kế thừa trong C++ [Lập trình hướng đối tượng với C++]