×

Cài đặt thuật toán Selection Sort trong lập trình

Avatar of admin
admin 1 Views

Trong quá trình phát triển phần mềm, việc sắp xếp mảng dữ liệu đóng vai trò rất quan trọng. Một trong những thuật toán sắp xếp phổ biến và dễ hiểu cho người mới học lập trình là Selection Sort. Thuật toán này sử dụng phương pháp chọn và hoán đổi để sắp xếp các phần tử trong mảng.

Nguyên lý hoạt động

Selection Sort hoạt động theo cách sau:

  1. Bắt đầu từ vị trí đầu tiên trong mảng, tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp.
  2. Hoán đổi phần tử nhỏ nhất tìm được với phần tử đang xét.
  3. Di chuyển đến vị trí tiếp theo và lặp lại quá trình trên cho đến khi toàn bộ mảng được sắp xếp.

Một số điểm cần lưu ý

  • Độ phức tạp thời gian: Selection Sort thực hiện n-1 lần so sánh cho mỗi phần tử, vậy nên độ phức tạp thời gian của nó là O(n^2) với n là số phần tử trong mảng. Điều này làm cho Selection Sort không hiệu quả đối với mảng có kích thước lớn.
  • Tính ổn định: Thuật toán này không phải là thuật toán ổn định, nghĩa là nó không duy trì thứ tự tương đối của các phần tử bằng nhau.

Triển khai thuật toán trong các ngôn ngữ lập trình

C++

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {
        int minIndex = i;
        
        for(int j = i+1; j < n; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Hoán đổi phần tử nhỏ nhất với phần tử ở vị trí i
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);

    selectionSort(arr, n);

    cout << "Mảng sau khi được sắp xếp: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Python

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_index = i
        
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Hoán đổi phần tử nhỏ nhất với phần tử ở vị trí i
        arr[i], arr[min_index] = arr[min_index], arr[i]

arr = [64, 25, 12, 22, 11]
selection_sort(arr)

print("Mảng đã được sắp xếp:", arr)

Ứng dụng thực tiễn

Mặc dù không tối ưu cho các tập dữ liệu lớn, Selection Sort vẫn có thể sử dụng trong các tình huống sau:

  • Các hệ thống có giới hạn tài nguyên, do thuật toán này rất đơn giản và yêu cầu bộ nhớ O(1) cho quá trình hoạt động.
  • Lập trình giáo dục, làm công cụ giảng dạy về các khái niệm cơ bản của thuật toán sắp xếp.

Kết luận

Qua việc tìm hiểu cách làm việc và triển khai thuật toán Selection Sort, chúng ta có cái nhìn rõ ràng hơn về một trong những thuật toán cơ bản và dễ tiếp cận trong lĩnh vực sắp xếp dữ liệu. Mặc dù có những hạn chế về hiệu suất, sự đơn giản và dễ hiểu của nó làm cho Selection Sort trở thành một công cụ học tập hiệu quả cho những người mới bắt đầu học lập trình.

Comments

Bài viết liên quan