Code Tu Tam

Thuật toán sắp xếp Selection sort (Sắp xếp lựa chọn) với Code C++

Rate this post

Chào mừng các bạn quay trở lại với code từ tâm. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++.

Bài viết đầu tiên này chúng ta sẽ cùng tìm hiểu về thuật toán sắp xếp selection sort hay còn gọi là sắp xếp lựa chọn. Nội dung bài viết bao gồm các phần sau:

Tư tưởng của thuật toán sắp xếp lựa chọn

Các bước mô phỏng thuật toán selection sort

Triển khai Code C++ cho thuật toán Selection Sort

một cách viết code đơn giản của tôi.

#include <iostream>
using namespace std;
void swap(int* x, int* y) {
	int t;
	t = *x;
	*y = *x;
	*y = t;
}
void printAray(int* arr, int n) {
        cout << "Giá tri của mảng sau khi sắp xếp là" << endl;
	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
}
void selectionSortArray(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		int min = i;
		for (int j = min + 1; j < n; j++) {
			if (arr[min] > arr[j]) {
				min = j;
			}
		}
		swap(arr[min], arr[i]);
	}
	printAray(arr, n);
}
int main()
{
	int arr[100];
	int n;
	cout << "Nhap vao so phan tu cua mang" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cout << "nhap phan tu arr[" << i << "]" << endl;
		cin >> arr[i];
	}
	selectionSortArray(arr, n);
}

Đánh giá Selection Sort

Độ phức tạp

Để chọn được phần tử nhỏ nhất, ta cần duyệt qua n phần tử (tốn n-1 phép so sánh) và sau đó hoán vị nó với phần tử đầu tiên của dãy hiện hành. Để tìm phần tử nhỏ nhất tiếp theo, ta cần duyệt qua n-1 phần tử (tốn n-2 phép so sánh). Cứ như vậy, ta thấy ngay thuật toán sẽ tốn (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) phép so sánh.

Mỗi lần duyệt, ta luôn phải hoán vị 1 lần (1 hoán vị tương đương với 3 phép gán), nghĩa là thuật toán sẽ tốn 3(n-1) + 3(n-2) + … + 3 = 3n(n-1)/2 = O(n2) phép gán.

Ưu điểm

Nhược điểm

Ứng dụng của thuật toán

Sắp xếp lựa chọn được sử dụng khi:

Thuật toán liên quan.

Tổng kết

Hy vọng qua bài viết về giải thuật sắp xếp Selection Sort (sắp xếp chọn) này sẽ giúp các bạn hiểu và vận dụng tốt vòng lặp for cũng như hiểu được ý tưởng của giải thuật này. Cũng khá thú vị đấy chứ nhỉ!

Cảm ơn các bạn đã theo dõi series thuật toán này.

Exit mobile version