Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đâ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 Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp selection sort. Nội dung bài viết bao gồm các phần sau:
- Ý tưởng của thuật toán
- Ví dụ minh họa
- Minh họa thuật toán sử dụng ngôn ngữ C++
- Đánh giá thuật toán
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu
Thuật toán selection sort là gì?
Thuật toán Selection Sort là một thuật toán sắp xếp đơn giản và dễ hiểu. Nó hoạt động bằng cách tìm kiếm phần tử nhỏ nhất trong mảng và đổi chỗ nó với phần tử đầu tiên. Sau đó, nó tìm kiếm phần tử nhỏ nhất trong phần còn lại của mảng và đổi chỗ nó với phần tử thứ hai, và tiếp tục như vậy cho đến khi toàn bộ mảng đã được sắp xếp.
Hiệu suất:
- Selection Sort không phải là một trong những thuật toán sắp xếp hiệu suất tốt nhất. Đối với một mảng có n phần tử, thuật toán này luôn phải thực hiện n-1 lượt so sánh và có thể cần thực hiện tối đa n-1 hoặc ít nhất 0 lượt hoán đổi. Vì vậy, độ phức tạp thời gian của Selection Sort là O(n^2), làm cho nó không phù hợp cho các dãy số lớn.
Ưu điểm:
- Đơn giản và dễ hiểu.
- Không đòi hỏi nhiều bộ nhớ bổ sung ngoài mảng đang sắp xếp.
Nhược điểm:
- Độ phức tạp thời gian tương đối cao cho các tập dữ liệu lớn.
- Không thay đổi thứ tự của các phần tử bằng nhau (không stable).
- Không hiệu quả khi đã có sẵn một dãy số gần sắp xếp.
Khi nào nên sử dụng:
- Selection Sort thường không được ưa chuộng trong các ứng dụng thời gian thực hoặc với các dãy số lớn.
- Nó có thể hữu ích trong trường hợp bạn cần sắp xếp một số phần tử nhỏ hoặc khi bạn muốn sử dụng một thuật toán đơn giản cho mục đích học tập hoặc biểu đồ hình vẽ.
Ý tưởng của thuật toán selection sort
Thuật toán selection sort sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(giả sử với sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng). Thuật toán sẽ chia mảng làm 2 mảng con
- Một mảng con đã được sắp xếp
- Một mảng con chưa được sắp xếp
Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.
Ví dụ minh họa
arr[] = 62 24 15 22 1 // Tìm phần tử nhỏ nhất trong 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 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 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 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++
// Code from https://nguyenvanhieu.vn
#include <stdio.h>
// 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("Sorted array: n");
printArray(arr, n);
return 0;
}
Kết quả chạy kiểm tra
Sorted array: 11 12 22 25 64
Đánh giá thuật toán selection sort
Độ phức tạp thuật toán
- Trường hợp tốt: O(n^2)
- Trung bình: O(n^2)
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(1)
Tóm lại, Selection Sort là một thuật toán đơn giản và dễ hiểu, nhưng nó không phải là lựa chọn tốt cho các tập dữ liệu lớn. Có nhiều thuật toán sắp xếp hiệu suất tốt hơn như Quick Sort, Merge Sort hoặc Heap Sort mà bạn có thể sử dụng để giải quyết các vấn đề sắp xếp lớn hơn và phức tạp hơn.
Nếu thấy bài viết hay và bổ ích, hay like và follow fanpage Học lập trình cùng Nguyễn Văn Hiếu để nhận thông báo về những bài viết mới nhất nhé.
Để lại một bình luận