Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Hôm nay chúng ta sẽ cùng tìm hiểu về thuật toán sắp xếp selection sort. Với những ví dụ minh họa và code sử dụng ngôn ngữ C++, bài viết này sẽ giúp bạn hiểu rõ hơn về cách hoạt động của thuật toán này.
Ý tưởng của thuật toán selection sort
Thuật toán selection sort hoạt động bằng cách tìm kiếm và đổi chỗ phần tử có giá trị nhỏ nhất (đối với sắp xếp tăng dần) trong đoạn chưa được sắp xếp. Sau đó, phần tử này được đưa vào đầu đoạn đã sắp xếp. Thuật toán này tiếp tục lặp lại quá trình trên cho đến khi cả mảng đã được sắp xếp.
Minh họa thuật toán selection sort
Ví dụ minh họa
Với một ví dụ đơn giản, giả sử chúng ta có mảng arr[] = 62, 24, 15, 22, 1. Quá trình sắp xếp sẽ diễn ra như sau:
- Tìm phần tử nhỏ nhất trong arr[0...4] và đổi chỗ nó với phần tử đầu tiên: [1] 24 15 22 62
- Tìm phần tử nhỏ nhất trong arr[1...4] và đổi chỗ nó với phần tử đầu tiên của arr[1...4]: 1 [15] 24 22 62
- Tìm phần tử nhỏ nhất trong arr[2...4] và đổi chỗ nó với phần tử đầu tiên của arr[2...4]: 1 15 [22] 24 62
- Tìm phần tử nhỏ nhất trong arr[3...4] và đổi chỗ nó với phần tử đầu tiên của arr[3...4]: 11 12 22 [24] 62
Minh họa thuật toán sử dụng ngôn ngữ C++
Dưới đây là đoạn code sử dụng ngôn ngữ C++ để triển khai thuật toán selection sort:
#include
// Hàm đổi chỗ 2 số nguyên
void swap(int &xp, int &yp) {
int temp = xp;
xp = yp;
yp = temp;
}
// Hàm selection sort
void selectionSort(int arr[], int n) {
int i, j, min_idx;
// Di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp
for (i = 0; i < n-1; i++) {
// Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên
swap(arr[min_idx], arr[i]);
}
}
/* Hàm xuất mảng */
void printArray(int arr[], int size) {
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Mảng sau khi sắp xếp:\n");
printArray(arr, n);
return 0;
} Kết quả chạy kiểm tra: Mảng sau khi sắp xếp: 11 12 22 25 64
Đánh giá thuật toán selection sort
Độ phức tạp thuật toán selection sort có thể được đánh giá như sau:
- Trường hợp tốt: O(n^2)
- Trường hợp trung bình: O(n^2)
- Trường hợp xấu nhất: O(n^2)
Tuy thuật toán này có độ phức tạp cao, nhưng với một số bài toán nhỏ hay đã có một phần tử đã ở đúng vị trí, selection sort có thể cho hiệu quả tương đối tốt.
Nếu bạn muốn theo dõi những bài viết mới nhất từ blog của Nguyễn Văn Hiếu, hãy like và follow fanpage Học lập trình cùng Nguyễn Văn Hiếu để không bỏ lỡ những nội dung bổ ích.
