Sắp xếp với thời gian tuyến tính

MayFest2024

Mở đầu

Ta đã làm quen với rất nhiều thuật toán sắp xếp. Độ phức tạp trung bình nhanh nhất trong các thuật toán sắp xếp là $O(n \log n)$ . Bạn có bao giờ tự hỏi rằng, ta có thể sắp xếp một mảng với độ phức tạp thời gian tuyến tính $O(n)$ không

Giải pháp

Counting sort

Nếu một mảng $A$ bao gồm $n$ số nguyên với phạm vi nhỏ $[L..R]$ (Ví dụ như tuổi thọ của một người chẳng hạn ). Ta có thể sử dụng thuật toán Counting Sort. Giả sử ta có mảng $A$ là $\{2,5,2,2,3,3\}$ . Ý tưởng của Counting Sort là:

Chuẩn bị một ‘mảng tần số’ $f$ với kích thước $k = R-L + 1$ và khởi tạo $f$ bằng các số $0$ . Trên mảng ví dụ đã cho ở trên, chúng ta có $L = 2, R = 5$ và $k = 4$ .
Chúng ta thực hiện một lần duyệt qua mảng $A$ và cập nhật tần số của mỗi số nguyên mà chúng ta thấy, tức là với mỗi $i ∈ [0.. n-1]$ , ta thực hiện $f [A [i] -L]++$ . Trên mảng ví dụ trên, chúng ta có $f [0] = 3, f [1] = 2, f [2] = 0, f [3] = 1$ .
Khi chúng ta biết tần số của mỗi số nguyên trong phạm vi nhỏ đó, ta tính tổng tiền tố của mỗi $i$ , tức là $f [i] = [f-1] + f [i]$ $∀i ∈ [1..k-1]$ . Bây giờ, $f [i]$ chứa số phần tử nhỏ hơn hoặc bằng $i$ . Trên mảng ví dụ trên, chúng ta có $f [0] = 3, f [1] = 5, f [2] = 5, f [3] = 6$ .
Tiếp theo, quay ngược lại từ $i = n-1$ xuống $i = 0$ . Chúng ta đặt $A [i]$ tại chỉ số $f [A [i] -L] -1$ vì nó là vị trí chính xác của $A [i]$ . Chúng ta giảm $f [A [i] -L]$ $1$ đơn vị để giá trị bản sao tiếp theo của $A [i]$ (nếu có) sẽ được đặt ngay trước $A [i]$ hiện tại. Trên mảng ví dụ ở trên, đầu tiên chúng ta đặt $A [5] = 3$ vào chỉ số $f [A [5] -2] -1 = f [1] -1 = 5-1 = 4$ và giảm $f [1]$ xuống $4$ đơn vị. Tiếp theo, đặt $A [4] = 3$ — cùng giá trị với $A [5] = 3$ — bây giờ ở chỉ số $f [A [4] -2] -1 = f [1] -1 = 4-1 = 3$ và giảm $f [1]$ xuống $3$ đơn vị. Sau đó, đặt $A [3] = 2$ vào chỉ số $f [A [3] -2] -1 = 2$ và giảm $f [0]$ xuống $2$ đơn vị. Chúng ta lặp lại ba bước tiếp theo cho đến khi có một mảng đã sắp xếp: $\{2, 2, 2, 3, 3, 5\}$ .

Độ phức tạp thời gian của Counting sort là $O (n + k)$ . Khi $k = O (n)$ , về mặt lý thuyết, thuật toán này chạy trong thời gian tuyến tính bằng cách không thực hiện so sánh các số nguyên. Tuy nhiên, trong môi trường cuộc thi lập trình thi đấu, thường $k$ không được quá lớn để tránh Vượt quá giới hạn bộ nhớ. Ví dụ: Counting sort sẽ gặp vấn đề khi sắp xếp mảng $A$ với $n = 3$ gồm các phần tử $\{1, 1000000000, 2\}$ vì nó có $k$ lớn.

Radix sort

Nếu mảng $A$ chứa $n$ số nguyên không âm với phạm vi tương đối rộng $[L..R]$ nhưng nó bao gồm số chữ số tương đối nhỏ, chúng ta có thể sử dụng thuật toán Radix sort.

Ý tưởng về Radix sort rất đơn giản. Đầu tiên, chúng ta tạo tất cả các số nguyên có $d$ chữ số — trong đó $d$ là số chữ số lớn nhất trong số nguyên lớn nhất trong $A$ — bằng cách thêm các số $0$ nếu cần. Sau đó, Radix Sort sẽ sắp xếp các số này theo từng chữ số, bắt đầu từ chữ số nhỏ nhất đến chữ số lớn nhất. Nó sử dụng một thuật toán stable sort khác như một quy trình con để sắp xếp các chữ số, chẳng hạn như Counting sort $O (n + k)$ được mô tả ở trên. Ví dụ:

Input: $d = 4$ : $\{323, 1257, 13, 322\}$
Thêm chữ số $0$ : $\{0323, 1257, 0013, 0322\}$
Sắp xếp theo chữ số thứ 4: $\{032(2), 032(3), 001(3), 125(7) \}$
Sắp xếp theo chữ số thứ 3: $\{00(1)3, 03(2)2, 03(2)3, 12(5)7\}$
Sắp xếp theo chữ số thứ 2: $\{0(0)13,1(2)57,0(3)22,0(3)23 \}$
Sắp xếp theo chữ số thứ 1: $\{(0)013,(0)322,(0)323, (1)257\}$

Đối với một mảng gồm $n$ số nguyên có $d$ chữ số, chúng ta sẽ thực hiện $O (d)$ lần Counting sort có độ phức tạp thời gian là $O (n + k)$ mỗi lần. Do đó, độ phức tạp về thời gian của Radix Sort là $O (d × (n + k))$ . Nếu chúng ta sử dụng Radix Sort để sắp xếp $n$ số nguyên có dấu 32 bit ( $≈ d = 10$ chữ số) và $k = 10$ . Thuật toán Radix Sort này chạy trong $O (10 × (n + 10))$ . Nó vẫn có thể được coi là chạy trong thời gian tuyến tính nhưng có hệ số không đổi cao.

Hãy thử áp dụng vào bài toán sau:

Bạn được cung cấp tuổi (tính theo năm) của tất cả người dân của một quốc gia có ít nhất 1 tuổi. Biết rằng không có cá nhân nào ở quốc gia đó sống từ 100 tuổi trở lên. Bây giờ, bạn được giao một nhiệm vụ rất đơn giản là sắp xếp tất cả các độ tuổi theo thứ tự tăng dần.

Input: Bao gồm nhiều testcases. Mỗi testcase bắt đầu bằng số nguyên $n (0 <n ≤ 2000000)$ , tổng số người. Trong dòng tiếp theo, có $n$ số nguyên cho biết tuổi. Đầu vào được kết thúc với trường hợp $n = 0$ .

Output: Đối với mỗi testcase, in ra một dòng với $n$ số nguyên cách nhau khoảng trắng. Các số nguyên này là tuổi của quốc gia đó được sắp xếp theo thứ tự tăng dần.

Chú ý: Input của bài toán khá lớn (∼ 25 MB), do đó bạn nên sử dụng faster IO.

Sample Input:

Sample Output:

1 2 3 4 5
1 2 2 3 3

Solution:

#include <iostream>

using namespace std;

const int Max = 100;
const int Min = 1;

// No need to use std::sort since can just store counts in array
int count[105];

int main()
{
    int N;
    while (cin >> N, N)
    {
        int age;

        for (int i = 0; i < N; ++i)
        {
            cin >> age;
            ++count[age];
        }

        string sep = "";
        for (int i = Min; i <= Max; ++i)
        {
            // This will counteract how --count[i] works
            // While leaving the count[i] == 0 after this iteration
            ++count[i];

            while (--count[i])
            {
                cout << sep << i;
                sep = " ";
            }
        }

        cout << '\n';
    }
}

Tổng kết

Xét sự phức tạp của việc viết mã cho Radix Sort so với việc gọi hàm sort chuẩn $O (n log n)$ C ++ STL (hoặc Java Collections.sort), thuật toán Radix Sort này hiếm khi được sử dụng trong các cuộc thi lập trình thi đấu. Do đó, việc gọi hàm vẫn là một lựa chọn tối ưu, nhanh và khỏe

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
Competitve programming 3 - Steven Halim, Felix Halim
onlinejudge.org
Algorithms in a nutshell - Geogre 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.

C++