Những giải thuật sắp xếp thú dzị

algorithm

10

Đang lượn lờ quora thì mình thấy có câu hỏi khá hay: What is the strangest sorting algorithm?. Tò mò vào đọc thì mình thấy có khá nhiều thuật toán thú dzị và tất nhiên là chưa nghe qua bao giờ. Với tinh thần vui là chính nên chọn ra 2 thuật toán theo mình là thú dzị nhât chia sẻ cho mọi người

1. Sleep sort

Ý tưởng của thuật toán này khá đơn giản: Với mỗi phần tử x của mảng, cho sleep x seconds rồi print phần tử đó ra màn hình. Đây là pseudo code của thuật toán này:

procedure printNumber(x)
    sleep x seconds
    print x
end

for arg in args
    run printNumber(arg) in background
end
wait for all processes to finish

Độ phức tạp của thuật toán này là O(max(args)). Chú ý là thuật toán này ko áp dụng được với mảng mà có phần tử là số âm nhé :D

2. Bogo sort

Theo wikipedia thì thuật toán này còn có những cái tên khác như: permutation sort, stupid sort, slowsort, shotgun sort or monkey sort. Đây có lẽ là thuật toán sắp xếp thú dzị nhất: sắp xếp dựa trên sự may mắn. Ý tưởng của thuật toán này cũng khá đơn giản: từ mảng input, ta ngẫu nhiên hoán đổi xáo trộn ngẫu nhiên các phần tử. Nếu kết quả là mảng đã sắp xếp thì coi như xong, còn nếu không thì ... cứ lặp lại cho đến khi sắp xếp đúng thứ tự. Nếu may mắn thì chỉ trong 1 lần xáo trộn duy nhất là ta được mảng đã sắp xếp. Tuy nhiên tỉ lệ may mắn cực kì thấp. Vì vậy Bogo Sort có độ phức tạp là O(vô cực), thật hài hước!. Còn dưới đây là pseudo code của thuật toán này, rất ngắn gọn và dễ hiểu phải ko nào :D

while not isInOrder(deck):
    shuffle(deck)

Dưới đây là pseudo code được viết bằng python:

import random

def is_sorted(data):
    for i in range(len(data) - 1):
        if data[i] > data[i + 1]:
            return False
    return True

def bogosort(data):
    while not is_sorted(data):
        random.shuffle(data)
    return data

Trên đây là những giải thuật sắp xếp theo mình là khá thú dzị. Các anh em nếu biết thêm giải thuật nào hay ho thì có thể chia sẻ ở phần comment nhé.

Tham khảo

[1] https://www.quora.com/What-is-the-strangest-sorting-algorithm
[2] https://www.quora.com/What-is-sleep-sort
[3] https://en.wikipedia.org/wiki/Bogosort