การเรียงแบบฟอง (bubble sort) ใน Python
ในบทเรียนนี้ คุณจะเขียนการเรียงแบบฟองและเพิ่มการหยุดก่อนกำหนดเมื่อลิสต์เรียงเสร็จแล้ว
บทนำ
ปัญหาที่ต้องแก้
การเรียงลำดับมีอยู่ทุกที่ และการเข้าใจว่ามันทำงานอย่างไรช่วยให้คุณคิดเรื่องความเร็วได้ 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²)
ประเด็นสำคัญ
result = values.copy()เรียงสำเนา ลิสต์ของผู้เรียกจึงไม่เปลี่ยนif result[index] > result[index + 1]:สลับคู่ที่ลำดับผิดendลดลงหลังทุกรอบ เพราะค่าที่ใหญ่ที่สุดอยู่ท้ายแล้วif not swapped: breakหยุดก่อนเมื่อรอบหนึ่งไม่มีการสลับ อินพุตที่เรียงแล้วจึงจบหลังรอบเดียว
ใช้เมื่อไร?
- เรียนรู้ว่าการเรียงแบบเปรียบเทียบทำงานอย่างไร
- ลิสต์เล็กมากในเครื่องมือการสอนและการแสดงภาพ
- ตรวจว่าลิสต์เรียงอยู่แล้วหรือไม่ในรอบเดียว
เมื่อไรยังไม่จำเป็น
- โปรแกรมจริงใดก็ตาม:
sorted()และlist.sort()เร็วกว่ามาก (O(n log n)) และผ่านการทดสอบ - ลิสต์ที่มีมากกว่าไม่กี่ร้อยรายการ: จำนวนการเปรียบเทียบโตตามกำลังสองของความยาว
ภาพจำลอง การเรียงแบบฟอง (bubble sort) ใน Python
O(n²)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
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]))
ผลลัพธ์จากการรัน
[1, 2, 4, 5, 8]
อธิบายโค้ด
หลังแต่ละรอบ ค่าที่ใหญ่ที่สุดของส่วนที่ยังไม่เรียงจะอยู่ในตำแหน่งสุดท้ายของมันแล้ว รอบถัดไปจึงสั้นลงหนึ่งตัว ตัวแปร swapped บอกว่าในรอบนั้นมีการสลับหรือไม่ ถ้าไม่มีเลย ลิสต์เรียงแล้วและลูปจะหยุดก่อน กรณีแย่ที่สุดความซับซ้อนเป็น O(n²) จึงไม่เหมาะกับข้อมูลขนาดใหญ่
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ไปเกินไปหนึ่งดัชนี
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]:
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- Count Inversions Count the out-of-order pairs in a list. ยาก
- ค่ามัธยฐานของลิสต์ หาค่ากลางของลิสต์หลังจากเรียงลำดับแล้ว ง่าย