Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:
Đề bài – Cho một mảng, cần sắp xếp mảng dùng Counting Sort.
Counting Sort làm việc trên key trong phạm vi cụ thể. Đếm số đối tượng có key khác nhau, tính toán vị trí, xuất kết quả.
Hãy quan sát giải pháp trong triển khai dưới đây:
Ví dụ
def countSort(arr):
# mảng output ký tự
output = [0 for i in range(256)]
# mảng count
count = [0 for i in range(256)]
# string bất biến
ans = ["" for _ in arr]
# đếm
for i in arr:
count[ord(i)] += 1
# vị trí trong output
for i in range(256):
count[i] += count[i-1]
# output
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1
# mảng ký tự sắp xếp
for i in range(len(arr)):
ans[i] = output[i]
return ans
# main
arr = "Tutorialspoint"
ans = countSort(arr)
print("Mảng ký tự đã sắp xếp:", "".join(ans))
Kết quả
Mảng ký tự đã sắp xếp: Taiilnooprsttu
Kết luận
Trong bài này, chúng ta đã học cách làm chương trình Python Counting Sort.