การเรียงลำดับแบบสับเปลี่ยน
 | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
 | บทความนี้ต้องการการจัดหน้า จัดหมวดหมู่ ใส่ลิงก์ภายใน หรือเก็บกวาดเนื้อหา ให้มีคุณภาพดีขึ้น คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้ป้ายข้อความอื่นเพื่อชี้ชัดข้อบกพร่อง |
การเรียงลำดับแบบสับเปลี่ยน (อังกฤษ: Bogosort หรือ Permutation 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)
การนำไปใช้งาน
[แก้]ตัวอย่างภาษาไพทอน
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!)