Thuật toán Selection Sort trong C++ là một giải thuật sắp xếp tăng dần dựa trên việc tìm và chọn phần tử nhỏ nhất trong mảng và sau đó chuyển nó đến vị trí đầu tiên. Giải thuật này lặp qua mảng nhiều lần, mỗi lần tìm phần tử nhỏ nhất và chuyển nó đến vị trí đầu tiên. Ví dụ về mã code của thuật toán Selection Sort trong C++ như sau:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n-1; i++) {
minIndex = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
for (int i=0; i < n; i++)
cout << arr[i] << " ";
return 0;
}Giải thích đoạn code trên
Đoạn code trên là một ví dụ về thuật toán Selection Sort trong ngôn ngữ lập trình C++.
Ở đoạn code này, ta có một mảng arr với n phần tử. Chúng ta sẽ lặp qua mảng này từ đầu đến cuối. Trong mỗi lần lặp, chúng ta sẽ tìm phần tử nhỏ nhất trong mảng và đặt nó vào vị trí đầu tiên. Sau đó, chúng ta sẽ di chuyển con trỏ đến vị trí tiếp theo trong mảng và lặp lại quá trình tìm và hoán vị cho đến khi mảng được sắp xếp hoàn toàn.
Thứ tự của phần tử trong mảng sẽ thay đổi sau mỗi lần lặp, đảm bảo rằng phần tử nhỏ nhất trong mảng luôn được đặt vào vị trí đầu tiên mỗi lần. Khi quá trình lặp hoàn tất, mảng sẽ được sắp xếp từ nhỏ đến lớn.
Các bài viết liên quan:
Độ phức tạp của selection sort
Độ phức tạp của thuật toán Selection Sort là O(n^2), trong đó n là số lượng phần tử cần sắp xếp. Độ phức tạp tồi tệ của thuật toán này là O(n^2), vì trong từng lần lặp, ta phải duyệt qua tất cả các phần tử còn lại trong mảng và tìm min. Vì vậy, thuật toán này chỉ được sử dụng khi số lượng phần tử trong mảng là nhỏ.
Các biến thể của Selection sort
Selection Sort có một số biến thể như:
- Selection Sort đơn giản: biến thể này sắp xếp mảng bằng cách tìm vị trí của giá trị nhỏ nhất và hoán đổi nó với giá trị đầu tiên.
- Selection Sort với đánh dấu: biến thể này sắp xếp mảng bằng cách sử dụng một mảng đánh dấu để xác định các phần tử đã được sắp xếp hoặc chưa.
Các biến thể trên cải tiến hoặc giảm thiểu độ phức tạp tối ưu hoặc thời gian chạy của thuật toán, nhưng vẫn giữ nguyên các bước cơ bản của Selection Sort.
Ưu điểm của thuật toán Selection sort
Selection sort có một số ưu điểm sau:
- Đơn giản: Cách hoạt động của Selection sort rất đơn giản và dễ hiểu, vì vậy nó rất dễ dàng để sử dụng và thực hiện.
- Độ phức tạp: Selection sort có độ phức tạp tính toán là O(n^2), nên nó rất hiệu quả cho các mảng nhỏ hoặc trung bình.
- Không cần bộ nhớ phụ: Selection sort không cần bộ nhớ phụ, vì vậy nó rất tốt cho hệ thống với số lượng bộ nhớ hạn hẹp.
- Chạy nhanh trên mảng nhỏ: Khi mảng chỉ có một số ít phần tử, Selection sort chạy nhanh hơn so với các thuật toán sắp xếp khác.
