Thuật Toán

MAYBE YOU MISS THESE SORTING ALGORITHMS

Bogosort (hay còn được gọi với nhiều cái tên trìu mến như stupid sort, slow sort hay random sort) là một trong những thuật toán sắp xếp “hữu hiệu” nhất từng được phát hiện. Cái tên “bogosort” là sự kết hợp giữa từ “bogus” (pha ke) và từ “sort”, nên ta có thể hiểu đây là một thuật toán sắp xếp pha ke. Bởi lẽ ý tưởng của thuật toán này là lần lượt tạo ra những hoán vị ngẫu nhiên của dãy số cho đến khi tìm được một hoán vị đã được sắp xếp.

Trong Python, ta có thể cài đặt thuật toán như sau:

from random import shuffle

def is_sorted(data):
    return all(data[i] <= data[i + 1] for i in range(len(data) - 1))
def bogosort(data):
    while not is_sorted(data):
        shuffle(data)
    return data

Với ý tưởng đầy “sáng tạo” như thế này, độ phức tạp trung bình của Bogosort rơi vào khoảng O(n!n), vì với mỗi hoán vị ta thực hiện nhiều nhất n-1 phép so sánh khi kiểm tra is_sorted và n-1 phép swap khi shuffle, cũng như lấy trung bình ta sẽ chỉ tạo ra nhiều nhất n! hoán vị của một dãy có n số.

Tuy nhiên, độ phức tạp này được xem là nhanh như gió nếu đặt lên bàn cân với thuật toán ông nội của Bogosort – chính là Bogobogosort (gấp đôi pha ke). Ý tưởng của nó cũng giống như Bogosort, chỉ khác là phiên bản ông nội này sẽ tập trung “cải tiến” hàm is_sorted ở trên bằng cách sử dụng đệ quy (nghe đệ quy lúc nào cũng ngầu hơn đúng không mọi người?).

Giả sử ta đang xếp dãy số tăng dần, để kiểm tra xem hoán vị hiện tại đã sắp xếp hay chưa, thuật toán này sẽ:

1. Tạo một dãy copy của dãy số gồm n giá trị.
2. Gọi đệ quy hàm bogobogosort với n-1 giá trị đầu của dãy copy.
3. Trong dãy copy, so sánh giá trị ở vị trí cuối cùng và giá trị lớn nhất trong n-1 giá trị đầu tiên:
+ Nếu lớn hơn, thì dãy copy đã được sắp xếp thành công, đi tới bước 4.
+ Ngược lại, ta shuffle dãy copy này và thực hiện lại bước 2.
4. So sánh dãy copy (đã được sắp xếp) và dãy ban đầu, nếu giống nhau thì chứng tỏ dãy ban đầu là một hoán vị đã sắp xếp.

Nói tóm lại, để kiểm tra xem hoán vị hiện tại đã được sắp xếp chưa, nó sẽ cố gắng tìm ra một hoán vị đã sắp xếp (??!!) và so sánh nó với hoán vị hiện tại (??!!).

Với ý tưởng như vậy, thật không ngạc nhiên khi cài đặt thuật toán này trong C++ và thử với một số bộ input, người ta thu được kết quả trong thời gian chạy như sau:


Để dễ hình dung hơn các bạn có thể xem Visualization của thuật toán Bogo Sort qua video của Timo Bingmann tại đây nhé: Bogo Sort – Youtube

Có thể thấy độ phức tạp của thuật toán này tăng rất nhanh, cũng như khá khó để dự đoán. Người ta dự đoán độ phức tạp của nó vào khoảng O((n!)n!), nhưng có người đã chứng minh độ phức tạp của nó “chỉ” vào khoảng O(n(n!)n). Nếu đặt lên bàn cân với Bogosort là O(n!n) thì có lẽ, cái cân đã bị gãy làm đôi và rơi sang một hành tinh khác, nơi 2 thuật toán này thuộc về.

Nguồn tham khảo: