โปรแกรม Python สำหรับ Cycle Sort

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

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

เป็นอัลกอริทึมแบบ in-place และการสลับ (swapping) เกิดขึ้นจากการสร้างวัฏจักร (cycles)

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

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

def cycleSort(array):
    writes = 0
    # วัฏจักรที่ต้องหมุน
    for cycleStart in range(0, len(array) - 1):
        item = array[cycleStart]
        # ตำแหน่งที่จะวาง item
        pos = cycleStart
        for i in range(cycleStart + 1, len(array)):
            if array[i] < item:
                pos += 1
        # หาก item อยู่แล้ว ไม่ใช่ cycle
        if pos == cycleStart:
            continue
        # มิฉะนั้น วาง item
        while item == array[pos]:
            pos += 1
        array[pos], item = item, array[pos]
        writes += 1
        # การหมุนต่อเนื่อง
        while pos != cycleStart:
            # หาตำแหน่งที่จะวาง item
            pos = cycleStart
            for i in range(cycleStart + 1, len(array)):
                if array[i] < item:
                    pos += 1
            # วาง item
            while item == array[pos]:
                pos += 1
            array[pos], item = item, array[pos]
            writes += 1
    return writes

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

ผลลัพธ์

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

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

สรุป

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