โปรแกรม Python สำหรับ BogoSort หรือ Permutation Sort

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดอาร์เรย์ ให้จัดเรียงโดยใช้แนวคิดของ Permutation Sort

BogoSort ที่รู้จักในชื่อ Permutation Sort อิงตามกระบวนสร้างและทดสอบ (generate and test paradigm)

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# โมดูล random
import random

# ฟังก์ชันจัดเรียง
def bogoSort(a):
    n = len(a)
    while (is_sorted(a) == False):
        shuffle(a)

# ตรวจสอบว่าจัดเรียงแล้วหรือยัง
def is_sorted(a):
    n = len(a)
    for i in range(0, n-1):
        if (a[i] > a[i+1]):
            return False
    return True

# สุ่มสลับ (permutation)
def shuffle(a):
    n = len(a)
    for i in range(0, n):
        r = random.randint(0, n-1)
        a[i], a[r] = a[r], a[i]

# โปรแกรมหลัก
a = [1, 5, 3, 4, 8, 6, 3, 4, 5]
bogoSort(a)
print("Sorted array :")
for i in range(len(a)):
    print(a[i], end=" ")

ผลลัพธ์

Sorted array is : 1 3 3 4 4 5 5 6 8

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ BogoSort หรือ Permutation Sort

หมายเหตุ: BogoSort มีประสิทธิภาพต่ำมาก (O(n!)) ใช้เพื่อการศึกษาหรือทดสอบเท่านั้น ไม่ควรใช้ในงานจริง