อัลกอริทึม Python

การเรียงแบบฟอง (bubble sort) ใน Python

ในบทเรียนนี้ คุณจะเขียนการเรียงแบบฟองและเพิ่มการหยุดก่อนกำหนดเมื่อลิสต์เรียงเสร็จแล้ว

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

การเรียงลำดับมีอยู่ทุกที่ และการเข้าใจว่ามันทำงานอย่างไรช่วยให้คุณคิดเรื่องความเร็วได้ bubble sort เป็นอัลกอริทึมเรียงลำดับที่ตามทีละขั้นได้ง่ายที่สุด จึงเป็นตัวอย่างแรกที่ใช้กันทั่วไป แม้โปรแกรมจริงจะใช้ตัวที่เร็วกว่า

ลองนึกภาพแบบนี้

bubble sort เหมือนการจัดแถวเด็กตามความสูงด้วยการสลับแค่เพื่อนที่อยู่ติดกัน เดินไปตามแถวแล้วสลับคู่ที่เด็กตัวสูงกว่าอยู่ข้างหน้า หลังเดินหนึ่งรอบ เด็กที่สูงที่สุดไปถึงท้ายแถว เหมือนฟองอากาศที่ลอยขึ้นสู่ผิวน้ำ ทำซ้ำจนเดินหนึ่งรอบแล้วไม่ต้องสลับเลย

จากการจัดแถวเด็กสู่โค้ด
result[index] > result[index + 1]👫 เด็กตัวสูงกว่าอยู่ข้างหน้าไหม?
result[index], result[index + 1] = ...🔄 สลับเพื่อนที่อยู่ติดกัน
for end in range(len(result) - 1, 0, -1):🚶 เดินตามแถวอีกครั้ง สั้นลงหนึ่งคนทุกครั้ง
if not swapped: break✅ เดินทั้งรอบแล้วไม่มีการสลับ: แถวเรียงแล้ว
หลังแต่ละรอบ ค่าที่ใหญ่ที่สุดที่เหลืออยู่ในตำแหน่งสุดท้ายของมัน
สรุปในประโยคเดียว

bubble sort เดินผ่านลิสต์ซ้ำๆ และสลับรายการที่อยู่ติดกันซึ่งลำดับผิด จนกว่าจะมีรอบที่ไม่มีการสลับเลย โดยทั่วไปใช้เวลา O(n²)

ประเด็นสำคัญ

  1. result = values.copy() เรียงสำเนา ลิสต์ของผู้เรียกจึงไม่เปลี่ยน
  2. if result[index] > result[index + 1]: สลับคู่ที่ลำดับผิด
  3. end ลดลงหลังทุกรอบ เพราะค่าที่ใหญ่ที่สุดอยู่ท้ายแล้ว
  4. if not swapped: break หยุดก่อนเมื่อรอบหนึ่งไม่มีการสลับ อินพุตที่เรียงแล้วจึงจบหลังรอบเดียว

ใช้เมื่อไร?

  • เรียนรู้ว่าการเรียงแบบเปรียบเทียบทำงานอย่างไร
  • ลิสต์เล็กมากในเครื่องมือการสอนและการแสดงภาพ
  • ตรวจว่าลิสต์เรียงอยู่แล้วหรือไม่ในรอบเดียว

เมื่อไรยังไม่จำเป็น

  • โปรแกรมจริงใดก็ตาม: sorted() และ list.sort() เร็วกว่ามาก (O(n log n)) และผ่านการทดสอบ
  • ลิสต์ที่มีมากกว่าไม่กี่ร้อยรายการ: จำนวนการเปรียบเทียบโตตามกำลังสองของความยาว

ภาพจำลอง การเรียงแบบฟอง (bubble sort) ใน Python

O(n²)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

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

รันโค้ด →
main.py
def bubble_sort(values):
    result = values.copy()
    for end in range(len(result) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swapped = True
        if not swapped:
            break
    return result

print(bubble_sort([5, 1, 4, 2, 8]))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

[1, 2, 4, 5, 8]

อธิบายโค้ด

หลังแต่ละรอบ ค่าที่ใหญ่ที่สุดของส่วนที่ยังไม่เรียงจะอยู่ในตำแหน่งสุดท้ายของมันแล้ว รอบถัดไปจึงสั้นลงหนึ่งตัว ตัวแปร swapped บอกว่าในรอบนั้นมีการสลับหรือไม่ ถ้าไม่มีเลย ลิสต์เรียงแล้วและลูปจะหยุดก่อน กรณีแย่ที่สุดความซับซ้อนเป็น O(n²) จึงไม่เหมาะกับข้อมูลขนาดใหญ่

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ไปเกินไปหนึ่งดัชนี

result[index + 1] ไปเลยท้ายเมื่อ index ถึงตำแหน่งสุดท้าย

ปัญหา
for index in range(len(result)):
    if result[index] > result[index + 1]:
วิธีแก้
for index in range(end):
    if result[index] > result[index + 1]:

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: การเรียงแบบผสาน (merge sort) ใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด