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ưởng của thuật toán
- Các bước mô phỏng
- Code thuật toán bằng C++
- Đánh giá thuật toán
- Một vài ứng dụng của thuật toán
Tư tưởng của thuật toán sắp xếp lựa chọn
- Ta chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về đầu dãy hiện hành.
- Sau đó, ta không quan tâm đến nó nữa, ta xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu tính từ vị trí thứ 2.
- Cứ vậy, cho đến khi dãy hiện hành chỉ còn 1 phần tử, ta được 1 dãy sắp tăng.
Các bước mô phỏng thuật toán selection sort
- 1. Đặt phần tử đầu tiên là min (nhỏ nhất)
- 2. So sánh min với phần tử thứ hai. Nếu phần tử thứ hai nhỏ hơn min, thì ta gán vị trí min sẽ là vị trí thứ hai (phần tử thứ 2).
So sánh min mới với phần tử thứ ba. Một lần nữa, nếu phần tử thứ ba nhỏ hơn, thì hãy gán giá trị tối thiểu cho phần tử thứ ba, nếu không thì không làm gì cả. Quá trình tiếp tục cho đến phần tử cuối cùng. - 3. Sau mỗi lần lặp lại, giá trị tại vị trí min sẽ được đưa về đầu danh sách chưa được sắp xếp.
- 4. Đối với mỗi lần lặp, lập chỉ mục bắt đầu từ phần tử chưa được sắp xếp đầu tiên. Ta lặp lại từ Bước 1 đến bước 3 cho đến khi tất cả các phần tử được đặt vào đúng vị trí của chúng.
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
- Thuật toán đơn giản, dễ hiện thực.
- Có số lần hoán đổi các vị trí ít.
Nhược điểm
- Chỉ được áp dụng trong các trường hợp có số lượng phần tử cần so sánh ít.
- Không nhận biết được mảng đã được sắp xếp.
Ứng dụng của thuật toán
Sắp xếp lựa chọn được sử dụng khi:
- Một danh sách nhỏ sẽ được sắp xếp
- Chi phí hoán đổi không thành vấn đề
- Kiểm tra tất cả các yếu tố là bắt buộc
- Chi phí ghi vào bộ nhớ quan trọng như trong bộ nhớ flash (số lần ghi / hoán đổi là O (n) so với O (n2) của bubble sort)
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.