huật toán sắp xếp chọn (Selection Sort) - Sắp xếp & tìm kiếm

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).

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

1. Thiết lập giá trị nhỏ nhất (min) về vị trí số 0.

2. Tạo vòng lặp for để di chuyển ranh giới của sorted list và unsorted list.

3. Tìm phần tử nhỏ nhất trong list chưa được sắp xếp.

4. 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.

5. 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àm selectionSort() để 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<<"	";
      }
}
 
int main()
{
    int n;
    int a[n];
    do{
        cout << "
Nhậ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: 
";
    printArray(a, n);
 
    cout<<"
---------------------------------------
";
    cout<<"Chương trình này được đăng tại Zaidap.com.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!!!