การเรียงลำดับแบบสับเปลี่ยน

การเรียงลำดับแบบสับเปลี่ยน () คือ ขั้นตอนวิธีการเรียงลำดับแบบสุ่มโดยมีวิธีคิดว่า สมมติว่าเรามีจำนวนเลขอยู่ 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)

 การนำไปใช้งาน 
ตัวอย่างภาษาไพทอน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

หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ
หมวดหมู่:การเรียงแบบเปรียบเทียบ