Thuật toán Bucket Sort là một trong những thuật toán sắp xếp hiệu quả, đặc biệt hữu dụng khi làm việc với dữ liệu phân phối đều hoặc có khoảng giá trị biết trước. Mục tiêu của thuật toán này là chia nhỏ tập dữ liệu vào các "bucket" (xô) và sau đó sắp xếp riêng lẻ từng bucket trước khi gộp lại thành mảng đã sắp xếp hoàn chỉnh.
Bước đầu tiên: Chuẩn bị dữ liệu và tạo các bucket
Để bắt đầu, dữ liệu cần được phân tích để xác định khoảng giá trị lớn nhất và nhỏ nhất. Dựa vào khoảng giá trị này, các bucket được khởi tạo. Ví dụ, nếu giá trị nhỏ nhất là 0 và giá trị lớn nhất là 100, có thể chia thành 10 bucket mỗi bucket chứa khoảng giá trị là 10 đơn vị (0-9, 10-19, ...).
def bucket_sort(arr):
if len(arr) == 0:
return arr
min_value = min(arr)
max_value = max(arr)
bucket_count = (max_value - min_value) // len(arr) + 1
buckets = [[] for _ in range(bucket_count)]
# Phân phối phần tử vào các bucket
for num in arr:
index = (num - min_value) // len(arr)
buckets[index].append(num)
# Sắp xếp từng bucket và nối lại thành mảng đã sắp xếp
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
Bước hai: Phân phối phần tử vào các bucket
Phần tử trong danh sách ban đầu được đưa vào các bucket dựa trên giá trị của chúng. Mỗi phần tử được phân bổ sao cho nó không vượt quá giới hạn bucket đã xác định. Điều này giảm tối thiểu số lần so sánh, giúp tăng tốc độ xử lý.
for num in arr:
index = (num - min_value) // len(arr)
buckets[index].append(num)
Bước ba: Sắp xếp từng bucket riêng rẽ
Mỗi bucket sau khi nhận được phần tử sẽ được sắp xếp. Thuật toán sắp xếp này có thể là bất cứ thuật toán nào như Quick Sort hay Merge Sort, nhưng thông thường sử dụng Insertion Sort do hiệu quả cao với các danh sách nhỏ.
for bucket in buckets:
sorted_bucket = sorted(bucket)
Bước bốn: Gộp các bucket lại thành mảng sắp xếp hoàn chỉnh
Sau khi tất cả các bucket đã được sắp xếp riêng rẽ, gộp chúng lại theo thứ tự ban đầu để tạo thành mảng cuối cùng đã được sắp xếp.
sorted_arr.extend(sorted_bucket)
Ví dụ cụ thể
Giả sử ta có mảng [3.5, 2.1, 5.7, 1.9, 3.3, 2.8, 5.9]. Ta có thể chia mảng này thành các bucket với khoảng cách là 1 đơn vị. Sẽ có các bucket như sau: [1-1.9, 2-2.9, 3-3.9, 4-4.9, 5-5.9].
arr = [3.5, 2.1, 5.7, 1.9, 3.3, 2.8, 5.9]
sorted_arr = bucket_sort(arr)
print(sorted_arr) # Output: [1.9, 2.1, 2.8, 3.3, 3.5, 5.7, 5.9]
Kết luận
Thuật toán này thường yêu cầu biết trước khoảng giá trị của dữ liệu đầu vào và hoạt động hiệu quả nhất với dữ liệu phân phối đều. Trong các trường hợp khác, việc thiết lập và quản lý các bucket có thể phức tạp, làm giảm hiệu quả tổng thể của thuật toán.
Với việc hiểu rõ và triển khai thành công thuật toán trên, bạn có thể tăng hiệu suất sắp xếp dữ liệu trong các ứng dụng thực tế, đồng thời góp phần làm nắm vững kiến thức về các thuật toán sắp xếp hiện đại.
Comments