SẮP XẾP & TÌM KIẾM
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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.

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.

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:

thuat toan selection sort png

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 listunsorted 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<<"\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ả:

sap xep chen selectionsort PNG

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!!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top