Quick Sort ใน Python
แยกค่าเป็นกลุ่มน้อยกว่า เท่ากับ และมากกว่า pivot
Quick Sort ใน Python คืออะไร?
แยกค่าเป็นกลุ่มน้อยกว่า เท่ากับ และมากกว่า pivot
แบ่งค่ารอบ pivot
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
ภาพจำลอง Quick Sort ใน Python
O(n log n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
main.py
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]หลักการทำงาน
เวลาเฉลี่ย O(n log n) แต่อาจเป็น O(n²) เมื่อเลือก pivot ไม่ดี
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น