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

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

ข้อความปัญหา — กำหนดรายการ (list) ให้ทำ Bitonic Sort บนรายการที่กำหนดและแสดงรายการ

Cocktail Sort — การจัดเรียงเกิดขึ้นคล้าย Bubble Sort ที่การวนรอบ (iteration) เกิดขึ้นในทั้งสองทิศทาง

อัลกอริทึม

อาร์เรย์จะถูกท่องจากซ้ายไปขวา ระหว่างการท่อง จะเปรียบเทียบรายการที่อยู่ติดกัน และสลับค่าตามเงื่อนไข ด้วยวิธีนี้ ตัวเลขมากที่สุดจะอยู่ที่ท้ายอาร์เรย์

จากนั้น อาร์เรย์จะถูกท่องในทิศทางตรงข้าม และสลับองค์ประกอบตามเงื่อนไข ด้วยวิธีนี้ ตัวเลขน้อยที่สุดจะอยู่ที่หน้าสุด

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

ตัวอย่าง

# ฟังก์ชัน
def cocktailSort(a):
    n = len(a)
    flag = True
    start = 0
    end = n-1
    while (flag == True):
        # เพื่อข้ามผลลัพธ์ของรอบก่อนหน้า
        flag = False
        # ท่องจากซ้ายไปขวา
        for i in range(start, end):
            if (a[i] > a[i+1]):
                a[i], a[i+1] = a[i+1], a[i]
                flag = True
        # หากไม่มีการสลับ แสดงว่าจัดเรียงแล้ว
        if (flag == False):
            break
        # มิฉะนั้น รีเซ็ต flag
        flag = False
        # รายการสุดท้ายจัดเรียงแล้ว
        end = end - 1
        # วนรอบจากขวาไปซ้าย
        for i in range(end-1, start-1, -1):
            if (a[i] > a[i+1]):
                a[i], a[i+1] = a[i+1], a[i]
                flag = True
        # องค์ประกอบแรกจัดเรียงแล้ว
        start = start + 1

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

ผลลัพธ์

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

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

สรุป

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