×

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

Avatar of admin
admin 0 Views

Radix Sort là một trong những thuật toán sắp xếp có hiệu suất cao, đặc biệt hữu ích khi làm việc với danh sách số nguyên lớn. Khác với các thuật toán sắp xếp so sánh truyền thống như Quick Sort hay Merge Sort, Radix Sort sử dụng phương pháp phân loại kỹ thuật số, nghĩa là nó không dựa vào việc so sánh trực tiếp các phần tử với nhau.

Cơ chế hoạt động của Radix Sort

Radix Sort làm việc bằng cách sắp xếp các số theo từng chữ số riêng lẻ, từ chữ số ít quan trọng nhất đến chữ số quan trọng nhất. Có hai phiên bản chính của thuật toán Radix Sort: LSD (Least Significant Digit) và MSD (Most Significant Digit). Bài viết này sẽ tập trung vào phiên bản LSD, vì nó phổ biến và dễ hiểu hơn.

Các bước triển khai Radix Sort

  1. Xác định số chữ số tối đa: Để biết phải duyệt bao nhiêu lần, cần xác định số chữ số lớn nhất trong các số cần sắp xếp.
  2. Sắp xếp theo chữ số hiện tại: Sử dụng một thuật toán phân loại ổn định như Counting Sort để sắp xếp các phần tử theo từng chữ số.

Cài đặt thuật toán Radix Sort bằng Python

Dưới đây là một ví dụ cụ thể về cách cài đặt thuật toán LSD Radix Sort bằng ngôn ngữ lập trình Python.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

if __name__ == "__main__":
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    print("Mảng ban đầu:", arr)
    radix_sort(arr)
    print("Mảng đã sắp xếp:", arr)

Trong đoạn mã trên, hàm counting_sort được sử dụng để sắp xếp các phần tử theo chữ số hiện tại (exp). Hàm radix_sort sẽ lặp lại quá trình này cho từng chữ số, bắt đầu từ chữ số ít quan trọng nhất (đơn vị) và sau đó là hàng chục, hàng trăm, v.v., cho đến chữ số quan trọng nhất.

Lợi ích và hạn chế của Radix Sort

Lợi ích:

  • Hiệu suất cao: Radix Sort có độ phức tạp thời gian là O(nk) với n là số lượng phần tử và k là số chữ số tối đa. Đối với các tập dữ liệu lớn và các số có số lượng chữ số không quá lớn, thời gian sắp xếp có thể rất nhanh.
  • Ổn định: Thuật toán giữ nguyên thứ tự của các phần tử có cùng giá trị, điều này quan trọng trong một số trường hợp cụ thể.

Hạn chế:

  • Phụ thuộc vào số chữ số: Đối với các số có rất nhiều chữ số hoặc trong trường hợp phải số hóa các đối tượng không phải số nguyên, Radix Sort có thể không thực sự phù hợp.
  • Bộ nhớ phụ thêm: Mặc dù không yêu cầu nhiều bộ nhớ như Merge Sort, Radix Sort vẫn cần một số bộ nhớ phụ cho các mảng tạm thời.

Tổng kết

Radix Sort là một thuật toán sắp xếp mạnh mẽ, đặc biệt là khi làm việc với các tập dữ liệu lớn và các số có độ dài chữ số nhỏ. Việc hiểu rõ cách cài đặt và ứng dụng của thuật toán này có thể giúp lập trình viên tối ưu hóa hiệu suất xử lý của các ứng dụng yêu cầu sắp xếp dữ liệu nhanh chóng và hiệu quả.

Comments

Bài viết liên quan