Test Set 1

Giống bubble sort, Trouble Sort có độ phức tạp thời gian \(O(N^2)\); chứng minh được trình bày ở phần dưới. Với \(N\le100\) trong Test Set 1, ta có thể chạy Trouble Sort đến khi kết thúc rồi duyệt danh sách kết quả để tìm lỗi sắp xếp đầu tiên nếu có, tức một giá trị lớn hơn giá trị ngay sau nó.

Test Set 2

Chạy Trouble Sort \(O(N^2)\) đến khi kết thúc là quá chậm khi \(N\le10^5\).

Thay vào đó, hãy phân tích việc Trouble Sort làm trong mỗi bước. Xét một danh sách đầu vào gồm 6 phần tử. Ở mỗi lượt duyệt mảng, Trouble Sort thực hiện các phép so sánh sau:

• Phần tử 0 \(\leftrightarrow\) phần tử 2.
• Phần tử 1 \(\leftrightarrow\) phần tử 3.
• Phần tử 2 \(\leftrightarrow\) phần tử 4.
• Phần tử 3 \(\leftrightarrow\) phần tử 5.

Bất kể độ dài danh sách là bao nhiêu, bảng trên cho thấy khiếm khuyết căn bản của Trouble Sort: phần tử ở chỉ số chẵn chỉ được so sánh với phần tử ở chỉ số chẵn khác, phần tử ở chỉ số lẻ chỉ được so sánh với phần tử ở chỉ số lẻ khác, còn phần tử chỉ số chẵn và chỉ số lẻ không bao giờ được so sánh với nhau! Điều đó có nghĩa Trouble Sort chỉ là bubble sort chạy riêng trên các phần tử chỉ số chẵn và các phần tử chỉ số lẻ, rồi đan xen chúng vào danh sách đầu ra. Trouble Sort chỉ đúng nếu việc đan xen hai danh sách con — danh sách chỉ số chẵn và danh sách chỉ số lẻ — tình cờ tạo ra một danh sách cũng đã sắp xếp. Vì có \(O(N)\) phần tử chỉ số chẵn, \(O(N)\) phần tử chỉ số lẻ và bubble sort có độ phức tạp \(O(N^2)\), Trouble Sort cũng có độ phức tạp \(O(N^2)\).

Để giải Test Set 2, ta dùng thuật toán sắp xếp \(O(N\log N)\) ưa thích trên từng danh sách con nói trên một cách độc lập, đan xen hai danh sách con đã sắp xếp, rồi tìm lỗi sắp xếp đầu tiên giống như trong lời giải Test Set 1.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Vòng loại, bài Trouble Sort; kho Google Coding Competitions Archive (Apache-2.0).