Thuật toán sắp xếp chọn – Selection Sort Algorithm C/C++

0
4508
thuat toan sap xep chon c

Thuật toán sắp xếp chọn, Seletion sort algorithm code C/C++. Chương trình cài đặt minh họa thuật toán sắp xếp chọn đổi chỗ trực tiếp sẽ giúp bạn hiểu rõ hơn về loại thuật toán này.

1. Ý tưởng thuật toán Selection sort

Sắp xếp chọn là một thuật toán sắp xếp đơn giản, dựa trên việc so sánh tại chỗ giống với việc sắp xếp tự nhiên. Tức là ta sẽ so sánh tất cả các phần tử trong danh sách với phần tử ở vị trí đang xét. Từ đó ta sẽ tìm được phần tử thích hợp nhất ở vị trí đó.

Giả sử xét với danh sách a có n phần tử. Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Giải thuật kết thúc khi phần tử cần tìm vị trí là phần tử cuối cùng.

2. Giải thuật Selection sort

Thuật toán:
Input: Mảng số nguyên a có n phần tử
Output: mảng a đã được sắp xếp

Bước 1 : i = 0
Bước 2 : Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành  từ  a[i] đến a[n-1]

  • Nếu min ¹ i: Đổi chỗ a[min] và a[i]
  • Nếu  i  < n:
  • i =i+1
  • Lặp lại Bước 2
  • Ngược lại: Dừng. //n phần tử đã nằm đúng vị trí

Lưu đồ thuật toán Sắp xếp chọn:

lưu đồ thuật toán sắp xếp chọn
lưu đồ thuật toán sắp xếp chọn

Cài đặt thuật toán Selection sort

   Với tư tưởng và thuật toán nêu ở phần trên, ta có thể cài đặt thuật toán bằng ngôn ngữ C++ như sau:

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[j]<a[min])
				min=j;
				
		if(min!=i)
		swap(a[i], a[min]);
	}
}

Dưới đây là chương trình viết bằng C++ về thuật toán này.

#include<iostream>
#include<time.h>
using namespace std;
void swap(int &a, int &b){
	a=a+b;
	b=a-b;
	a=a-b;
}
// Thuat toan sap xep chon
void selectionSort(int a[], int n){
	int min;
	for(int i=0;i<n-1;i++){
		min=i;
		for(int j=i; j<n;j++)
			if(a[j]<a[min])
				min=j;
				
		if(min!=i)
		swap(a[i], a[min]);
	}
}

// input arr and sort
void solve(){
	int a[100];  // khai báo mảng tối đa 100 phần tử
	int n;

	// Nhap mang
	cout<<"Nhap n: "; cin>>n;
    
    for(int i=0;i<n;i++)
        cin>>a[i];
        
    // goi ham sap xep
    selectionSort(a,n);
}

int main(){
    solve();
    printf("\nDone!");
}

LEAVE A REPLY

Please enter your comment!
Please enter your name here