การเรียงแบบเร็ว (quick sort) ใน Python
ในบทเรียนนี้ คุณจะเขียนการเรียงแบบเร็ว โดยแบ่งลิสต์รอบสมาชิกตัวหลัก (pivot)
บทนำ
ปัญหาที่ต้องแก้
quicksort เป็นแนวคิดการเรียงลำดับที่ใช้กันแพร่หลายที่สุดแบบหนึ่ง เพราะโดยเฉลี่ยแล้วเร็วและเขียนได้ง่าย quicksort แสดงให้เห็นอีกวิธีในการแบ่งโจทย์: แทนที่จะแบ่งตรงกลาง เราแบ่งโดยเทียบกับค่าที่เลือกไว้
ลองนึกภาพแบบนี้
quicksort เหมือนการเรียงหนังสือตามความสูง โดยใช้หนังสือเล่มหนึ่งที่เลือกไว้เป็นตัวเทียบ เล่มที่เตี้ยกว่าวางกองซ้าย เล่มที่สูงกว่าวางกองขวา เล่มที่สูงเท่ากันวางไว้ตรงกลาง จากนั้นเรียงกองแต่ละข้างด้วยวิธีเดียวกัน แล้วนำทุกกองมาเรียงต่อกัน
pivot = values[len(values) // 2]📕 เลือกหนังสือหนึ่งเล่มไว้เปรียบเทียบlower = [... if value < pivot]⬅️ หนังสือที่เตี้ยกว่าไปทางซ้ายhigher = [... if value > pivot]➡️ หนังสือที่สูงกว่าไปทางขวาquick_sort(lower) + equal + quick_sort(higher)📚 เรียงแต่ละข้าง แล้วรวมกองquicksort เลือก pivot (ค่าตัวเทียบ) หนึ่งตัว แบ่งค่าอื่นเป็นกลุ่มที่เล็กกว่าและกลุ่มที่ใหญ่กว่า pivot เรียงแต่ละกลุ่มแบบเรียกซ้ำ แล้วนำมาต่อกัน ใช้เวลาโดยเฉลี่ย O(n log n)
ประเด็นสำคัญ
if len(values) <= 1:คือ base case: ลิสต์แบบนี้เรียงอยู่แล้วpivot = values[len(values) // 2]เอาค่าตรงกลางเป็น pivotlower,equalและhigherแบ่งค่าโดยเทียบกับ pivot และequalเก็บค่าที่ซ้ำกันไว้ด้วยกันquick_sort(lower) + equal + quick_sort(higher)เรียงสองข้าง แล้วต่อทั้งสามลิสต์เข้าด้วยกัน
ใช้เมื่อไร?
- เรียนรู้การแบ่งส่วน (partitioning) และ recursion
- การเรียงแบบ in-place (แก้ไขลิสต์เดิมโดยตรง) สำหรับงานทั่วไปในภาษาและไลบรารีต่าง ๆ (โดยเลือก pivot อย่างระมัดระวัง)
- โจทย์การเลือก เช่น การหามัธยฐาน (quickselect ใช้การแบ่งแบบเดียวกัน)
เมื่อไรยังไม่จำเป็น
- โค้ด Python ทั่วไป:
sorted()เร็วกว่าและเป็นแบบ stable - เมื่อต้องรับประกันเวลาในกรณีแย่สุด: pivot ที่เลือกไม่ดีทำให้ quicksort ช้าเป็น
O(n²)ส่วน merge sort ไม่มีวันช้าขนาดนั้น
ภาพจำลอง การเรียงแบบเร็ว (quick sort) ใน Python
O(n log n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
ผลลัพธ์จากการรัน
[1, 5, 7, 8, 9, 10]
อธิบายโค้ด
เวอร์ชันที่อ่านง่ายนี้เลือกสมาชิกตรงกลางเป็นตัวหลัก และสร้างลิสต์สามชุด lower, equal และ higher ด้วย list comprehension ผลลัพธ์คือการต่อ quick_sort(lower), equal และ quick_sort(higher) เข้าด้วยกัน ความซับซ้อนเฉลี่ยคือ O(n log n) แต่ถ้าเลือกตัวหลักไม่ดีอาจช้าลงถึง O(n²)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ทิ้งค่าที่เท่ากับ pivot
ถ้าแบ่งด้วยแค่ < และ > ค่าที่เท่ากับ pivot จะหายไป
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
โจทย์ทั้งหมด