Tìm hiểu thuật toán sắp xếp chọn (Selection Sort)

byHiếu Nguyễn • • 2 min read
0

Trong lĩnh vực khoa học máy tính, thuật toán sắp xếp là một chủ đề quan trọng và được áp dụng rộng rãi. Trong số các thuật toán sắp xếp phổ biến, thuật toán sắp xếp chọn (Selection Sort) là một giải pháp đơn giản và dễ hiểu. Trong bài viết này, chúng ta sẽ cùng nhau thảo luận và tìm hiểu về thuật toán sắp xếp chọn, cách hoạt động của nó và cách triển khai thuật toán này.

Khái niệm thuật toán sắp xếp chọn

Thuật toán sắp xếp chọn (tiếng Anh: Selection sort) là thuật toán được thiết kế để sắp xếp một danh sách dữ liệu theo thứ tự tăng dần hoặc giảm dần bằng cách chọn ra phần tử nhỏ nhất hoặc lớn nhất để đưa về vị trí đúng của nó. Quá trình này lặp đi lặp lại cho đến khi mảng được sắp xếp hoàn toàn.

Cách thức hoạt động của thuật toán sắp xếp chọn

Thuật toán sắp xếp chọn được thực hiện theo các bước sau:
  • Bước 1: Xác định phần tử nhỏ nhất (hoặc lớn nhất) của dãy và hoán đổi nó với phần tử tại vị trí đầu tiên.
  • Bước 2: Xác định phần tử nhỏ nhất (hoặc lớn nhất) của phần còn lại chưa được sắp xếp ở bên phải và hoán đổi nó với phần tử ở vị trí tiếp theo.
  • Bước 3: Lặp lại quá trình cho đến khi dãy được sắp xếp hoàn toàn.
Giả sử ta có mảng arr = {24, 33, 3, 37, 10, 26} và ta cần sắp xếp theo thứ tự tăng dần, ta thực hiện thuật toán như sau:
  • Đầu tiên, ta đặt i = 24 là vị trí ta sẽ hoán đổi với phần tử nhỏ nhất, và lướt phần còn lại của mảng để xác định phần tử nhỏ nhất. Sau khi duyệt hết phần tử, ta xác định 3 là phần tử nhỏ nhất. Vậy ta sẽ tiến hành tráo 3 với 24.
  • Sau đó, ta dời i sang phần tử tiếp theo là 33 và tiếp tục xác định số nhỏ nhất của phần còn lại. Sau khi duyệt, ta xác định trong phần chưa được sắp xếp (không kể số 3 đã được đặt đúng vị trí), phần tử nhỏ nhất là 10. Vậy ta tiếp tục tiến hành hoán đổi 10 và 33 cho nhau.
  • Tiếp tục dời i qua 24 và lướt phần còn lại của mảng. Ta xác định bản thân 24 nhỏ nhất nên giữ nguyên vị trí phần tử này.
  • Dời i qua 37 và lặp lại các bước trên một lần nữa. Ta xác định 26 nhỏ nhất nên ta đổi 26 với 37 cho nhau.
  • Dời i qua phần tử tiếp theo là 33. Vì bản thân 33 là phần tử nhỏ nhất rồi, nên ta giữ nguyên vị trí của nó.
  • Vậy là xong bước cuối cùng, ta có mảng đã được sắp xếp hoàn toàn.

Triển khai thuật toán

Sau đây là code triển khai thuật toán sắp xếp chọn bằng những ngôn ngữ khác nhau mà bạn có thể tham khảo.

C

#include <stdio.h>

// Hàm xuất mảng
void printArr(int arr[], int arrLength)
{
    for (int i = 0; i < arrLength; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Hàm sắp xếp
void selectionSort(int arr[], int arrLength)
{
    // Vòng lặp lướt mảng từ đầu tới phần tử gần cuối mảng
    for (int i = 0; i < arrLength - 1; i++)
    {
        // Cho i là vị trí của phần tử nhỏ nhất
        int minIndex = i;
        // Vòng lặp for lồng để lướt phần còn lại của mảng
        for (int j = i + 1; j < arrLength; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                // Nếu phần tử tại vị trí j nhỏ hơn phần tử tại minIndex thì ta thay đổi biến minIndex
                minIndex = j;
            }
        }
        
        // Xác định được phần tử nhỏ nhất, hoán đổi phần tử này với phần tử tại vị trí i cho nhau
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {24, 33, 3, 37, 10, 26};
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    
    printf("Mang ban dau: ");
    printArr(arr, arrLength);

    selectionSort(arr, arrLength);

    printf("Mang da duoc sap xep: ");
    printArr(arr, arrLength);

    return 0;
}

C++

#include <iostream>

using namespace std;

// Hàm xuất mảng
void printArr(int arr[], int arrLength)
{
    for (int i = 0; i < arrLength; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Hàm sắp xếp
void selectionSort(int arr[], int arrLength)
{
    // Vòng lặp lướt mảng từ đầu tới phần tử gần cuối mảng
    for (int i = 0; i < arrLength - 1; i++)
    {
        // Cho i là vị trí của phần tử nhỏ nhất
        int minIndex = i;
        // Vòng lặp for lồng để lướt phần còn lại của mảng
        for (int j = i + 1; j < arrLength; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                // Nếu phần tử tại vị trí j nhỏ hơn phần tử tại minIndex thì ta thay đổi biến minIndex
                minIndex = j;
            }
        }
        
        // Xác định được phần tử nhỏ nhất, hoán đổi phần tử này với phần tử tại vị trí i cho nhau
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {24, 33, 3, 37, 10, 26};
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Mang ban dau: ";
    printArr(arr, arrLength);

    selectionSort(arr, arrLength);

    cout << "Mang da duoc sap xep: ";
    printArr(arr, arrLength);

    return 0;
}

C#

using System;

namespace Main
{
    class Program
    {
        // Phương thức xuất mảng
        static void printArr(int[] arr)
        {
            foreach (int i in arr)
            {
                Console.Write($"{i} ");
            }
            Console.WriteLine();
        }
        
        // Phương thức sắp xếp
        static void selectionSort(int[] arr)
        {
            // Vòng lặp lướt mảng từ đầu tới phần tử gần cuối mảng
            for (int i = 0; i < arr.Length - 1; i++)
            {
                // Cho i là vị trí của phần tử nhỏ nhất
                int minIndex = i;
                // Vòng lặp for lồng để lướt phần còn lại của mảng
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[minIndex])
                    {
                        // Nếu phần tử tại vị trí j nhỏ hơn phần tử tại minIndex thì ta thay đổi biến minIndex
                        minIndex = j;
                    }
                }
                
                // Xác định được phần tử nhỏ nhất, hoán đổi phần tử này với phần tử tại vị trí i cho nhau
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        
        static void Main()
        {
            int[] arr = {24, 33, 3, 37, 10, 26};
            
            Console.Write("Mang ban dau: ");
            printArr(arr);
            
            selectionSort(arr);
            
            Console.Write("Mang da duoc sap xep: ");
            printArr(arr);
        }
    }
}

Java

import java.util.Arrays;

public class Main {
    // Phương thức sắp xếp
    public static void selectionSort(int[] arr) {
        // Vòng lặp lướt mảng từ đầu tới phần tử gần cuối mảng
        for (int i = 0; i < arr.length - 1; i++) {
            // Cho i là vị trí của phần tử nhỏ nhất
            int minIndex = i;
            // Vòng lặp for lồng để lướt phần còn lại của mảng
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    // Nếu phần tử tại vị trí j nhỏ hơn phần tử tại minIndex thì ta thay đổi biến minIndex
                    minIndex = j;
                }
            }

            // Xác định được phần tử nhỏ nhất, hoán đổi phần tử này với phần tử tại vị trí i cho nhau
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {24, 33, 3, 37, 10, 26};

        System.out.println("Mang ban dau: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Mang da duoc sap xep: " + Arrays.toString(arr));
    }
}

Python

# Hàm sắp xếp
def selectionSort(lst):
    # Vòng lặp lướt danh sách từ đầu tới phần tử gần cuối danh sách
    for i in range(len(lst) - 1):
        # Cho i là vị trí của phần tử nhỏ nhất
        minIndex = i
        # Vòng lặp for lồng để lướt phần còn lại của danh sách
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[minIndex]:
                # Nếu phần tử tại vị trí j nhỏ hơn phần tử tại minIndex thì ta thay đổi biến minIndex
                minIndex = j
        
        # Xác định được phần tử nhỏ nhất, hoán đổi phần tử này với phần tử tại vị trí i cho nhau
        lst[i], lst[minIndex] = lst[minIndex], lst[i]

lst = [24, 33, 3, 37, 10, 26]

print(f"Danh sách ban đầu: {lst}")
selectionSort(lst)
print(f"Danh sách đã được sắp xếp: {lst}")

JavaScript

// Hàm sắp xếp
function selectionSort(arr) {
    // Vòng lặp lướt mảng từ đầu tới phần tử gần cuối mảng
    for (let i = 0; i < arr.length - 1; i++) {
        // Cho i là vị trí của phần tử nhỏ nhất
        let minIndex = i;
        // Vòng lặp for lồng để lướt phần còn lại của mảng
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                // Nếu phần tử tại vị trí j nhỏ hơn phần tử tại minIndex thì ta thay đổi biến minIndex
                minIndex = j;
            }
        }

        // Xác định được phần tử nhỏ nhất, hoán đổi phần tử này với phần tử tại vị trí i cho nhau
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

let arr = [24, 33, 3, 37, 10, 26];

window.alert("Mảng ban đầu: " + arr);
selectionSort(arr);
window.alert("Mảng đã được sắp xếp: " + arr);

Phân tích độ phức tạp về thời gian và bộ nhớ

Độ phức tạp về thời gian

  • Trong trường hợp tốt nhất, trung bình và xấu nhất, độ phức tạp thời gian của thuật toán sắp xếp chọn đều là O(n^2), trong đó n là số lượng phần tử trong danh sách cần sắp xếp.
  • Quá trình lặp lại để tìm phần tử nhỏ nhất (hoặc lớn nhất) trong danh sách cần sắp xếp và đặt nó vào vị trí đúng mất O(n) thao tác. Vì vậy, tổng số thao tác lặp lại là O(n) * O(n) = O(n^2).
  • Dù có thể tối ưu hơn một số thuật toán sắp xếp khác, thuật toán sắp xếp chọn vẫn có độ phức tạp thời gian tương đối cao khi số lượng phần tử lớn.

Độ phức tạp về bộ nhớ

  • Độ phức tạp không gian của thuật toán sắp xếp chọn là O(1), tức là không cần bất kỳ không gian bộ nhớ phụ nào ngoài danh sách ban đầu.
  • Thuật toán hoạt động trực tiếp trên danh sách đầu vào và không tạo thêm cấu trúc dữ liệu hay mảng bổ sung. Vì vậy, không gian bổ sung được sử dụng cố định và không phụ thuộc vào kích thước danh sách đầu vào.

Ưu điểm và hạn chế của thuật toán sắp xếp chọn

Ưu điểm

  • Đơn giản và dễ hiểu: Thuật toán sắp xếp chọn có cấu trúc đơn giản và dễ hiểu, không đòi hỏi kiến thức phức tạp để triển khai. Người dùng có thể nhanh chóng hiểu và áp dụng thuật toán này.
  • Độ phức tạp về bộ nhớ thấp: Như đã phân tích ở trên, thuật toán sắp xếp chọn không yêu cầu tạo thêm bất kỳ cấu trúc dữ liệu nào, và chỉ hoạt động trực tiếp trên danh sách đầu vào mà thôi. Điều này giúp tiết kiệm bộ nhớ khi sắp xếp.

Hạn chế

Ngoài các ưu điểm kể trên, thuật toán sắp xếp chọn có các hạn chế cần lưu ý sau:
  • Kém hiệu quả với danh sách lớn: Như đã phân tích độ phức tạp về thời gian ở trên, thuật toán sắp xếp chọn không phù hợp với danh sách lớn. Với độ phức tạp về thời gian là O(n^2), khi danh sách đầu vào có kích thước càng lớn, thời gian để thực hiện thuật toán này cũng tăng rất nhanh theo bình phương, khiến cho việc sắp xếp trở nên tốn thời gian và kém hiệu quả.
  • Không ổn định: Thuật toán sắp xếp chọn không đảm bảo tính ổn định. Điều này có nghĩa là các phần tử có cùng giá trị có thể thay đổi thứ tự sau khi sắp xếp. Nếu tính ổn định là yếu tố quan trọng, thuật toán sắp xếp chọn không phải là lựa chọn tốt.

Ứng dụng

Mặc dù thuật toán sắp xếp chọn không hiệu quả cho tập dữ liệu lớn, nó vẫn có thể được áp dụng trong một số trường hợp cụ thể. Dưới đây là một số ứng dụng của thuật toán sắp xếp chọn:
  • Sắp xếp mảng nhỏ: Với các mảng nhỏ có kích thước tương đối nhỏ, thuật toán sắp xếp chọn vẫn có thể được sử dụng. Do độ phức tạp thời gian tuyến tính, thuật toán cho phép sắp xếp nhanh chóng các mảng có kích thước nhỏ.
  • Sắp xếp danh sách gần được sắp xếp hoàn toàn: Nếu danh sách ban đầu đã gần như được sắp xếp hoàn toàn, thuật toán sắp xếp chọn có thể hiệu quả vì phần chưa được sắp xếp của danh sách chỉ còn một ít, việc chọn phần tử nhỏ nhất (hoặc lớn nhất) để sắp xếp nốt cũng không tốn thời gian nhiều.
  • Mục đích giảng dạy và học tập: Thuật toán sắp xếp chọn thường được sử dụng để giảng dạy và học tập về thuật toán sắp xếp. Vì cấu trúc đơn giản và dễ hiểu, nó thường được sử dụng như một ví dụ để giải thích khái niệm và cách hoạt động của thuật toán sắp xếp.

Kết

Thuật toán sắp xếp chọn là một giải pháp đơn giản cho việc sắp xếp dữ liệu. Mặc dù có độ phức tạp thời gian cao so với một số thuật toán sắp xếp khác, nhưng nó vẫn có ưu điểm là dễ hiểu và dễ triển khai. Đối với các tập dữ liệu nhỏ hoặc khi đơn giản làm quen với thuật toán sắp xếp, thuật toán chọn là một lựa chọn hợp lý.

Tuy nhiên, trong trường hợp cần sắp xếp các tập dữ liệu lớn, nên xem xét sử dụng các thuật toán sắp xếp khác có độ phức tạp thời gian tốt hơn như thuật toán sắp xếp nhanh (Quick Sort) hoặc thuật toán sắp xếp trộn (Merge Sort). Điều này giúp tăng hiệu suất và giảm thời gian thực thi.

Hi vọng bài viết này đã giúp bạn hiểu về thuật toán sắp xếp chọn và cách triển khai nó. Việc nắm vững các thuật toán sắp xếp là một kỹ năng quan trọng trong lĩnh vực khoa học máy tính và có thể được áp dụng trong nhiều tình huống khác nhau.
Tags:
4.94 / 12.043 rates

Đăng nhận xét

Mới hơn Cũ hơn