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

Counting Sort là một thuật toán sắp xếp không so sánh, hoạt động dựa trên việc đếm số lượng các mục với giá trị riêng biệt. Việc này giúp xác định vị trí của từng phần tử trong mảng đã sắp xếp. Phương pháp này đặc biệt hiệu quả khi các phần tử đầu vào có phạm vi giá trị nhỏ. Dưới đây là hướng dẫn chi tiết về cách cài đặt thuật toán Counting Sort trong lập trình.

Nguyên lý hoạt động

1. Xác định phạm vi giá trị của đầu vào: Đầu tiên, cần xác định giá trị lớn nhất và nhỏ nhất trong mảng đầu vào để biết được phạm vi cần lưu trữ.

2. Tạo mảng đếm: Tạo một mảng đếm để lưu trữ số lần xuất hiện của mỗi giá trị trong mảng đầu vào.

3. Cộng dồn giá trị: Biến đổi mảng đếm thành mảng chứa các vị trí cuối cùng của các giá trị trong mảng đã sắp xếp.

4. Sắp xếp phần tử: Dùng mảng đếm để quyết định vị trí của các phần tử trong mảng đã sắp xếp và sao chép chúng vào mảng kết quả.

Các bước cài đặt

Để minh hoạ cụ thể, chúng ta sẽ sử dụng ngôn ngữ lập trình Python để cài đặt thuật toán Counting Sort.

Bước 1: Xác định phạm vi giá trị

Đầu tiên, cần tìm giá trị lớn nhất và nhỏ nhất trong mảng để xác định phạm vi giá trị của đầu vào.

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1

Bước 2: Tạo mảng đếm

Tiếp theo, tạo một mảng đếm với kích thước bằng với phạm vi giá trị đã xác định ở bước trên.

    count_array = [0] * range_of_elements

Bước 3: Tính số lần xuất hiện của mỗi giá trị trong mảng đầu vào

Duyệt qua mảng đầu vào và đếm số lần xuất hiện của mỗi phần tử.

    for num in arr:
        count_array[num - min_val] += 1

Bước 4: Cộng dồn giá trị trong mảng đếm

Biến đổi mảng đếm thành mảng vị trí bằng cách cộng dồn các giá trị.

    for i in range(1, len(count_array)):
        count_array[i] += count_array[i - 1]

Bước 5: Sắp xếp phần tử

Tạo mảng kết quả và đặt các phần tử vào vị trí chính xác trong mảng đếm.

    output_array = [0] * len(arr)
    for num in reversed(arr):
        output_array[count_array[num - min_val] - 1] = num
        count_array[num - min_val] -= 1

Bước 6: Sao chép mảng

Cuối cùng, sao chép các phần tử từ mảng kết quả trở lại mảng đầu vào.

    for i in range(len(arr)):
        arr[i] = output_array[i]
    return arr

Code hoàn chỉnh

Dưới đây là đoạn mã hoàn chỉnh cho thuật toán Counting Sort trong Python:

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1
    
    count_array = [0] * range_of_elements
    for num in arr:
        count_array[num - min_val] += 1
    
    for i in range(1, len(count_array)):
        count_array[i] += count_array[i - 1]
    
    output_array = [0] * len(arr)
    for num in reversed(arr):
        output_array[count_array[num - min_val] - 1] = num
        count_array[num - min_val] -= 1
    
    for i in range(len(arr)):
        arr[i] = output_array[i]

    return arr

# Khởi chạy hàm với một mảng ví dụ
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

Kết luận

Counting Sort là một thuật toán rất hiệu quả đối với các mảng có phạm vi giá trị nhỏ. Việc cài đặt thuật toán này không quá phức tạp nhưng lại cung cấp một cách sắp xếp nhanh chóng và tối ưu cho những trường hợp đặc biệt. Tuy nhiên, nó không phù hợp với các trường hợp có phạm vi giá trị lớn hoặc yêu cầu sắp xếp động. Hãy cân nhắc khi sử dụng Counting Sort để đạt hiệu quả tốt nhất.