Bogosort

Bogo Sort คือ ขั้นตอนวิธีการเรียงลำดับแบบสุ่มโดยมีวิธีคิดว่า สมมุติว่าเรามีจำนวนเลขอยู่1ชุดให้เราทำการสุ่มชุดตัวเลขที่มีอยู่จากนั้นให้เราทำการตรวจสอบว่าตัวเลขที่สุ่มมีการเรียงลำดับหรือไม่ หากยังไม่เรียงลำดับให้เราทำการสุ่มชุดตัวเลขไปเรื่อยๆ จนกว่าชุดตัวเลขจะทำการเรียงลำดับจนเสร็จสมบูรณ์

ตัวอย่าง

สมมุติว่าเรามีจำนวนชุดตัวเลข ( 5 1 4 2 8 )

สุ่มตัวเลขครั้งที่ 1 ( 8 5 1 4 2) สุ่มตัวเลขครั้งที่ 2 ( 5 8 4 1 2)

สุ่มตัวเลขครั้งที่ 3 ( 2 4 1 5 8) สุ่มตัวเลขครั้งที่ n ( 1 2 4 5 8)

เราสามารถทำการเรียงลำดับจนเสร็จสมบูรณ์ได้ ( 1 2 4 5 8)

การนำ Bogo Sort ไปใช้งานในภาษาPython

ตัวอย่างภาษาไพทอน

def bogosort(collection):
    

    def isSorted(collection):
        if len(collection) < 2:
            return True
        for i in range(len(collection) - 1):
            if collection[i] > collection[i + 1]:
                return False
        return True

    while not isSorted(collection):
        random.shuffle(collection)
        
    return collection

จากโค้ดข้างบนจะมีความซับซ้อน(complexity)เป็น O(n!) เพราะเป็นการเรียงแบบสุ่ม ไม่มีกฏเกณฑ์ที่ชัดเจน หากคำนวณมันเป็นเรียงสลับเปลี่ยนตำแหน่งที่เป็นไปได้ของข้อมูลทั้งหมด (n!)

อ้างอิง

• BogoSort on WikiWikiWeb