อัลกอริทึม Python

การเรียงแบบเร็ว (quick sort) ใน Python

ในบทเรียนนี้ คุณจะเขียนการเรียงแบบเร็ว โดยแบ่งลิสต์รอบสมาชิกตัวหลัก (pivot)

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

บทนำ

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

quicksort เป็นแนวคิดการเรียงลำดับที่ใช้กันแพร่หลายที่สุดแบบหนึ่ง เพราะโดยเฉลี่ยแล้วเร็วและเขียนได้ง่าย quicksort แสดงให้เห็นอีกวิธีในการแบ่งโจทย์: แทนที่จะแบ่งตรงกลาง เราแบ่งโดยเทียบกับค่าที่เลือกไว้

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

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

จากกองหนังสือสู่โค้ด
pivot = values[len(values) // 2]📕 เลือกหนังสือหนึ่งเล่มไว้เปรียบเทียบ
lower = [... if value < pivot]⬅️ หนังสือที่เตี้ยกว่าไปทางซ้าย
higher = [... if value > pivot]➡️ หนังสือที่สูงกว่าไปทางขวา
quick_sort(lower) + equal + quick_sort(higher)📚 เรียงแต่ละข้าง แล้วรวมกอง
แบ่งข้อมูลโดยเทียบกับ pivot แล้วเรียงแต่ละข้างด้วยวิธีเดียวกัน
สรุปในประโยคเดียว

quicksort เลือก pivot (ค่าตัวเทียบ) หนึ่งตัว แบ่งค่าอื่นเป็นกลุ่มที่เล็กกว่าและกลุ่มที่ใหญ่กว่า pivot เรียงแต่ละกลุ่มแบบเรียกซ้ำ แล้วนำมาต่อกัน ใช้เวลาโดยเฉลี่ย O(n log n)

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

  1. if len(values) <= 1: คือ base case: ลิสต์แบบนี้เรียงอยู่แล้ว
  2. pivot = values[len(values) // 2] เอาค่าตรงกลางเป็น pivot
  3. lower, equal และ higher แบ่งค่าโดยเทียบกับ pivot และ equal เก็บค่าที่ซ้ำกันไว้ด้วยกัน
  4. 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)

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

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

รันโค้ด →
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]))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

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

[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

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

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

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

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

ทิ้งค่าที่เท่ากับ pivot

ถ้าแบ่งด้วยแค่ < และ > ค่าที่เท่ากับ pivot จะหายไป

ปัญหา
return quick_sort(lower) + [pivot] + quick_sort(higher)
วิธีแก้
return quick_sort(lower) + equal + quick_sort(higher)

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

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

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

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

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