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:
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);
}Để 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.
Sắp xếp lựa chọn được sử dụng khi:
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.
Bình luận: