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[แก้]

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

 1 def bogosort(collection):
 2     
 3 
 4     def isSorted(collection):
 5         if len(collection) < 2:
 6             return True
 7         for i in range(len(collection) - 1):
 8             if collection[i] > collection[i + 1]:
 9                 return False
10         return True
11 
12     while not isSorted(collection):
13         random.shuffle(collection)
14         
15     return collection

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

อ้างอิง[แก้]