Thuật toán sắp xếp chọn (Selection Sort)

Posted on Updated on by adminChuyên mục:Kiến thức Internet

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

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau khám phá về sắp xếp chọn là gì. Cách tiến hành thuật toán trong C + + và ví dụ đơn cử vận dụng thuật toán để những 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 thuần. Nó triển khai việc làm so sánh những thành phần trong list .

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í tiên phong trong list, tiếp đến sẽ là vị trí nhỏ thứ hai liên tục được tráo đổi ngay sau vị trí nhỏ nhất .

Ví dụ minh họa:

thuat toan selection sort png

Như những bạn thấy ở hình trên. Ở Step1, list bắt đầu là 7 5 4 2. Trong list, số 2 là nhỏ nhất vì thế chọn số 2 vào sorted list và thay thế sửa chữa 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, tất cả chúng ta mở màn 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 giờ đây 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 những thành phần 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 thành phần 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, tất cả chúng ta sẽ thực hành thực tế một bài toán đơn thuầ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 
#include 
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["<> 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ả:

sap xep chen selectionsort PNG

Như vậy là tất cả chúng ta đã triển khai xong chương trình sắp xếp mảng bằng chiêu thức 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 những bạn thực thi thành công xuất sắc ! ! !

admin