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

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

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

Counting Sort เป็นเทคนิคที่ทำงานบนคีย์ (keys) ในช่วงเฉพาะ เกี่ยวข้องกับการนับจำนวนวัตถุที่มีคีย์และค่าที่แตกต่างกัน สุดท้ายเราทำการคำนวณเลขคณิตเพื่อหาตำแหน่งของแต่ละวัตถุและแสดงผลลัพธ์

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

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

def countSort(arr):
    # อาร์เรย์ตัวอักษรสำหรับผลลัพธ์ที่จัดเรียงแล้ว
    output = [0 for i in range(256)]
    # สร้าง count array เริ่มต้นด้วย 0
    count = [0 for i in range(256)]
    # เนื่องจากสตริงเป็น immutable
    ans = ["" for _ in arr]
    # นับ
    for i in arr:
        count[ord(i)] += 1
    # ตำแหน่งของตัวอักษรใน output array
    for i in range(256):
        count[i] += count[i-1]
    # อาร์เรย์ตัวอักษรผลลัพธ์
    for i in range(len(arr)):
        output[count[ord(arr[i])]-1] = arr[i]
        count[ord(arr[i])] -= 1
    # อาร์เรย์ตัวอักษรที่จัดเรียงแล้ว
    for i in range(len(arr)):
        ans[i] = output[i]
    return ans

# โปรแกรมหลัก
arr = "Tutorialspoint"
ans = countSort(arr)
print("Sorted character array is " + "".join(ans))

ผลลัพธ์

Sorted character array is Taiilnooprsttu

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

สรุป

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