Mở đầu
Trong lập trình, việc sắp xếp mảng là một trong những nhiệm vụ quan trọng mà chúng ta thường gặp. Độ phức tạp thời gian trung bình nhanh nhất của các thuật toán sắp xếp phổ biến như Quicksort hay Heapsort là O(n log n). Liệu chúng ta có thể đạt được độ phức tạp thời gian tuyến tính O(n) hay không? Trong bài viết này, chúng ta sẽ khám phá hai thuật toán sắp xếp có thể đạt được điều này: Counting Sort và Radix Sort.
Giải pháp 1: Counting Sort
Thuật toán Counting Sort phù hợp khi chúng ta cần sắp xếp một mảng các số nguyên với phạm vi giá trị khá nhỏ. Giả sử chúng ta có mảng A chứa n số nguyên trong khoảng từ L đến R. Dưới đây là quy trình hoạt động của Counting Sort:
- Chuẩn bị mảng tần số: Tạo một mảng tần số f với kích thước k = R - L + 1 và khởi tạo tất cả giá trị trong f bằng 0.
- Đếm tần số: Duyệt qua mảng A và cập nhật mảng tần số f với mỗi phần tử xuất hiện trong A.
- Tính tổng tiền tố: Chúng ta tính tổng tiền tố cho mỗi chỉ số trong mảng f, giúp xác định vị trí cuối cùng của mỗi phần tử trong mảng đã sắp xếp.
- Xác định vị trí cho từng phần tử: Bắt đầu từ cuối mảng A, di chuyển về đầu mảng, và đặt từng phần tử vào vị trí chính xác trong mảng đã sắp xếp, giảm giá trị trong mảng f sau mỗi lần chèn.
Độ phức tạp thời gian của Counting Sort là O(n + k). Trong trường hợp k = O(n), thuật toán này hoạt động với thời gian tuyến tính. Tuy nhiên, cần lưu ý rằng thuật toán này không hiệu quả khi k quá lớn so với n.
Giải pháp 2: Radix Sort
Radix Sort là một thuật toán khác mà chúng ta có thể sử dụng để sắp xếp các số nguyên không âm với phạm vi rộng, nhưng số chữ số lại khá nhỏ. Cách thức hoạt động của Radix Sort bao gồm:
- Chọn số chữ số lớn nhất: Tìm số chữ số lớn nhất trong mảng A.
- Tiếp cận từng chữ số: Sử dụng Counting Sort để sắp xếp mảng A theo từng chữ số, bắt đầu từ chữ số nhỏ nhất đến chữ số lớn nhất.
- Lặp lại cho tất cả các chữ số: Tiến hành sắp xếp cho đến khi tất cả các chữ số của mọi phần tử đều được sắp xếp.
Với n số nguyên có d chữ số, độ phức tạp thời gian của Radix Sort sẽ là O(d × (n + k)). Đối với số nguyên 32 bit, giá trị d thường là 10, cho nên Radix Sort cũng có thể coi như chạy trong thời gian tuyến tính với k = 10.
Bài toán ứng dụng
Giả sử bạn được giao nhiệm vụ sắp xếp tuổi của tất cả người dân trong một quốc gia (tuổi tối đa là 99). Bạn cần thực hiện như sau:
Input: Nhiều testcase, bắt đầu với số nguyên n (0 < n ≤ 2000000), số lượng người. Dòng tiếp theo chứa n số nguyên, mỗi số là tuổi.
Kết thúc với trường hợp n = 0.
Output: Đối với mỗi testcase, in ra tuổi đã sắp xếp theo thứ tự tăng dần.
Ví dụ đầu vào:
5
3 4 2 1 5
5
2 3 2 3 1
0Kết quả đầu ra:
1 2 3 4 5
1 2 2 3 3Kết luận
Mặc dù Radix Sort và Counting Sort là những thuật toán có thể giải quyết bài toán sắp xếp trong thời gian tuyến tính, trong thực tiễn, việc sử dụng các hàm sắp xếp tiêu chuẩn như std::sort trong C++ hoặc Collections.sort trong Java vẫn thường được ưa chuộng hơn do tính hiệu quả và đơn giản của chúng.
Tài liệu tham khảo
- Giải thuật và lập trình - Thầy Lê Minh Hoàng
- cp-algorithms.com
- Handbook Competitive Programming - Antti Laaksonen
- Competitive Programming 3 - Steven Halim, Felix Halim
- onlinejudge.org
- Algorithms in a nutshell - George T. Heineman, Gary Pollice & Stanley Selkow
- Tài liệu giáo khoa chuyên tin 2 - Hồ Sĩ Đàm, Đỗ Đức Đông, Lê Minh Hoàng & Nguyễn Thanh Hùng.
source: viblo
