Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp chọn (Selection Sort)
Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp chọn (Selection Sort). Đây là một trong những thuật toán sắp xếp căn bản trong C++.
Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp chọn là gì. Cách triển khai thuật toán trong C++ và ví dụ cụ thể áp dụng thuật toán để các bạn hiểu rõ hơn.
1. Sắp xếp chọn là gì?
Sắp xếp chọn là một trong những thuật toán đơn giản. Nó thực hiện công việc so sánh các phần tử trong danh sách.
Danh sách chứa các phần tử sẽ được chia làm hai phần. Phần ở bên trái là phần được sắp xếp (sort list) và phần ở bên phải là phần chưa được sắp xếp (unsorted list).
Bài viết này được đăng tại [free tuts .net]
Ban đầu chưa được sắp xếp thì phần sorted list sẽ trống và phần unsorted list sẽ chứa tất cả các phần tử ban đầu.
Phần tử nhỏ nhất trong list sẽ được chọn và tráo đổi với vị trí đầu tiên trong list, tiếp đến sẽ là vị trí nhỏ thứ hai tiếp tục được tráo đổi ngay sau vị trí nhỏ nhất.
Ví dụ minh họa:
Như các bạn thấy ở hình trên. Ở Step1, list ban đầu là 7 5 4 2. Trong list, số 2 là nhỏ nhất vì vậy chọn số 2 vào sorted list và thay thế vị trí số 7. Như vậy phần sorted list đã có số 2 và phần unsorted list còn lại 3 số là 5 4 7.
Ở Step2, chúng ta bắt đầu tìm số nhỏ thứ hai trong list đó là số 4. Tiếp tục chọn số 4 vào sorted list ở vị trí ngay sau số 2 là số nhỏ nhất. Trong sorted list bây giờ có hai số là 2 5 và unsorted list còn lại hai số là 5 7.
Cứ như vậy Step3 và Step4 sẽ tìm số nhỏ tiếp theo trong list và chọn vào sorted list, cho đến khi các phần tử trong list đã sắp xếp xong.
Thuật toán sắp xếp chọn (Selection Sort) trong C++.
Trong phần này mình sẽ đưa ra các bước để viết thuật toán, sau đó sẽ để thuật toán mình đã viết cho các bạn dễ hình dung.
Giải thích thuật toán
-
Thiết lập giá trị nhỏ nhất (min) về vị trí số 0.
-
Tạo vòng lặp for để di chuyển ranh giới của sorted list và unsorted list.
-
Tìm phần tử nhỏ nhất trong list chưa được sắp xếp.
-
Sau khi tìm được phần tử nhỏ nhất thì đổi chỗ phần tử đó với phần tử đầu tiên. Ở bước này chúng ta cần viết một hàm
Swap(), hàm này mình sẽ viết ở bên dưới. -
Lặp lại cho tới khi list được sắp xếp xong.
Thuật toán sắp xếp chọn
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 swap():
void swap(int &xp, int &yp)
{
int temp = xp;
xp = yp;
yp = temp;
}Ví dụ sắp xếp chọn trong mảng
Trong phần ví dụ sắp xếp chọn này, chúng ta sẽ thực hành một bài toán đơn giản đó là:
- Tạo mảng gồm các phần tử được nhập từ bàn phím.
- Tiến hành sắp xếp các phần tử sử dụng phương pháp sắp xếp chọn.
- Hiển thị mảng đã sắp xếp ra màn hình.
Gợi ý:
- Việc đầu tiên sẽ viết hàm
swap()để thực hiện công việc tráo đổi vị trí khi tìm được phần tử nhỏ nhất trong mảng. - Tiếp đến viết hàm
selectionSort()để thực hiện công việc sắp xếp các phần tử trong mảng. - Viết hàm
printSort()để in mảng đã được sắp xếp. - Tạo mảng gồm các phần tử được nhập từ bàn phím trong hàm
main(). Gọi hàmselectionSort()để sắp xếp. - Cuối cùng gọi hàm
printSort()để in mảng ra màn hình.
Code mẫu:
#include <stdio.h>
#include <iostream>
using namespace std;
// 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++){
cout << arr[i];
cout<<"\t";
}
}
int main()
{
int n;
int a[n];
do{
cout << "\nNhập vào số lượng phần tử có trong mảng: ";
cin >> n;
}while(n <= 0);
for(int i = 0;i < n;i++){
cout<<"a["<<i<<"]=";
cin >> a[i];
};
selectionSort(a, n);
cout<<"Mảng sau khi được sắp xếp: \n";
printArray(a, n);
cout<<"\n---------------------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp mảng bằng phương pháp sắp xếp chọn. Cũng như kết thúc hướng dẫn thuật toán sắp xếp chon (Selection Sort) trong C++. Chúc các bạn thực hiện thành công!!!
