การเรียงลำดับ (Sorting)

การเรียงลำดับเป็นพื้นฐานที่ใช้บ่อย และเป็นหัวข้อคลาสสิกในการเรียนอัลกอริทึม ในงานจริงเราใช้ sorted() ของภาษาเลย (ซึ่งเป็น O(n log n) ที่ปรับแต่งมาดีแล้ว) แต่ควรเข้าใจหลักการเบื้องหลังและ complexity เพื่อตอบสัมภาษณ์และเลือกใช้เป็น

ในงานจริง: ใช้ sorted() และ .sort()

nums = [3, 1, 4, 1, 5, 9, 2]

print(sorted(nums))               # [1,1,2,3,4,5,9] (คืนลิสต์ใหม่)
print(sorted(nums, reverse=True)) # [9,5,4,3,2,1,1] (มากไปน้อย)

nums.sort()                       # เรียงในตัวเอง (ของเดิมเปลี่ยน)

# เรียงตามเงื่อนไขด้วย key
words = ["banana", "kiwi", "apple"]
print(sorted(words, key=len))     # ['kiwi','apple','banana'] (ตามความยาว)

people = [{"name": "A", "age": 30}, {"name": "B", "age": 20}]
print(sorted(people, key=lambda p: p["age"]))  # เรียงตามอายุ

Bubble Sort — เข้าใจง่ายแต่ช้า O(n²)

เปรียบเทียบสมาชิกคู่ที่อยู่ติดกัน สลับถ้าผิดลำดับ ทำซ้ำจนไม่มีอะไรต้องสลับ ตัวที่ใหญ่สุดจะ "ลอย" ไปท้ายเหมือนฟองอากาศ — จึงชื่อ bubble

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # สลับ
    return arr

print(bubble_sort([5, 2, 8, 1, 9]))  # [1, 2, 5, 8, 9]

หลักการของ Merge Sort และ Quick Sort

สอง algorithm นี้เร็วกว่า (O(n log n)) ด้วยแนวคิด "แบ่งแล้วพิชิต" (divide and conquer) ไม่ต้องท่อง implement เป๊ะ แต่ควรเข้าใจไอเดีย

• Merge Sort: แบ่งลิสต์ครึ่ง ๆ จนเหลือตัวเดียว แล้วค่อย ๆ รวม (merge) กลับแบบเรียงลำดับ — เสถียร แต่ใช้หน่วยความจำเพิ่ม
• Quick Sort: เลือกตัว "pivot" แล้วแบ่งของที่น้อยกว่าไปซ้าย มากกว่าไปขวา แล้วทำซ้ำกับแต่ละฝั่ง — เร็วในทางปฏิบัติ แต่ worst case O(n²)

สรุปหัวข้อนี้

• งานจริงใช้ sorted() (คืนใหม่) หรือ .sort() (ในตัว) — ปรับ key และ reverse ได้
• Bubble sort O(n²): เปรียบเทียบคู่ติดกันแล้วสลับ เข้าใจง่ายแต่ช้า
• Merge/Quick sort O(n log n): ใช้แนวคิดแบ่งแล้วพิชิต เร็วกว่ามากเมื่อ n ใหญ่
• เข้าใจ complexity และไอเดีย พอสำหรับสัมภาษณ์ — ไม่ต้องท่อง implement ทุกตัว