การค้นหาและการจัดเรียง

การค้นหา (searching) และการจัดเรียง (sorting) คือจุดที่ Big-O กลายเป็นสิ่งที่ สัมผัสได้จริง — ความต่างระหว่าง O(n) กับ O(log n) หรือ O(n²) กับ O(n log n) ไม่ใช่แค่ตัวเลขบนกระดาษ แต่คือความต่างระหว่างโปรแกรมที่ตอบในพริบตากับโปรแกรมที่ค้างไปหลายวินาที บทเรียนนี้ยังเป็นแบบฝึกการตัดสินใจ: AI สร้างฟังก์ชันจัดเรียงให้ได้ห้าแบบในไม่กี่วินาที แต่มีแค่คุณเท่านั้นที่บอกได้ว่าแบบไหนถูกต้อง แบบไหนเร็วพอ และแบบไหน เสถียร (stable) — คุณสมบัติที่มักถูกมองข้ามจนไปพังระบบจริงแบบเงียบ ๆ

การค้นหาเชิงเส้น vs การค้นหาทวิภาค

การค้นหาเชิงเส้น (linear search) คือการไล่ดูทีละตัวตั้งแต่ต้นจนเจอ (หรือจนหมดรายการ) ทำงานได้กับข้อมูลทุกแบบ ไม่ต้องเรียงลำดับมาก่อน แต่กรณีเลวร้ายต้องดูครบทุกตัว จึงเป็น O(n)

การค้นหาทวิภาค (binary search) เร็วกว่ามากที่ O(log n) แต่มีเงื่อนไขสำคัญ: ข้อมูลต้องเรียงลำดับมาก่อน แล้วเท่านั้น

แนวคิดคือ “ตัดครึ่ง” (halving): มองที่ค่ากลางของช่วง

• ถ้าค่ากลาง = ค่าที่หา → เจอแล้ว
• ถ้าค่ากลาง < ค่าที่หา → ค่าที่หาต้องอยู่ครึ่งขวา ทิ้งครึ่งซ้ายไป
• ถ้าค่ากลาง > ค่าที่หา → ค่าที่หาต้องอยู่ครึ่งซ้าย ทิ้งครึ่งขวาไป

ทุกก้าวตัดข้อมูลที่เหลือทิ้งครึ่งหนึ่ง ข้อมูล ๑,๐๐๐,๐๐๐ ตัว ใช้แค่ราว ๒๐ ก้าวก็เจอ (เพราะ log₂(1,000,000) ≈ 20) เทียบกับการค้นหาเชิงเส้นที่อาจต้องดูถึงล้านครั้ง

การค้นหาทวิภาค อย่างระมัดระวัง

binary search เขียนผิดง่ายอย่างน่าตกใจ จุดพลาดยอดฮิตคือขอบเขตของ lo, mid, hi และ off-by-one (พลาดไปหนึ่ง) จนเกิดวนไม่รู้จบหรือข้ามค่าที่ต้องเจอ นี่คือเวอร์ชันที่ถูกต้อง:

def binary_search(arr, target):
    lo = 0
    hi = len(arr) - 1        # hi ชี้ดัชนีตัวสุดท้ายที่ "ยังเป็นไปได้"

    while lo <= hi:          # ต้องเป็น <= ไม่ใช่ < เพื่อตรวจช่วงที่เหลือ 1 ตัว
        mid = (lo + hi) // 2 # หารปัดลง ได้ดัชนีกลาง
        if arr[mid] == target:
            return mid       # เจอแล้ว คืนดัชนี
        elif arr[mid] < target:
            lo = mid + 1     # ตัดครึ่งซ้ายทิ้ง (+1 กันค้าง)
        else:
            hi = mid - 1     # ตัดครึ่งขวาทิ้ง (-1 กันค้าง)

    return -1                # ไม่เจอ

จุดที่ต้องระวัง:

• hi = len(arr) - 1 ไม่ใช่ len(arr) — เพราะ hi คือดัชนีของตัวสุดท้ายที่ยังพิจารณาอยู่
• while lo <= hi ต้องใช้ <= ไม่ใช่ < มิฉะนั้นช่วงที่เหลือเพียง ๑ ตัวจะไม่ถูกตรวจ
• lo = mid + 1 และ hi = mid - 1 ต้องมี +1/-1 เสมอ ถ้าเขียน lo = mid หรือ hi = mid เมื่อช่วงแคบเหลือ ๒ ตัว mid จะไม่ขยับ → วนไม่รู้จบ

เคล็ดลับกันบั๊ก: ใช้ mid = lo + (hi - lo) // 2 แทน (lo + hi) // 2 ในภาษาที่จำนวนเต็มมีขีดจำกัด (เช่น Java/C++) เพื่อกัน integer overflow — ใน Python ไม่จำเป็นเพราะ int ขยายได้ไม่จำกัด

ภาพรวมการจัดเรียง

อัลกอริทึมจัดเรียงที่เรียนกันส่วนใหญ่เป็น comparison sort คือตัดสินใจจากการ “เปรียบเทียบ” ค่าทีละคู่ว่าตัวไหนมาก่อน ที่เหลือของบทเรียนนี้จะแบ่งอัลกอริทึมเป็นสองกลุ่ม: กลุ่ม O(n²) ที่ง่าย ควรเข้าใจให้ลึกแต่แทบไม่ได้เขียนใช้จริงในโปรดักชัน กับกลุ่ม O(n log n) ที่อยู่เบื้องหลัง standard library ทุกภาษาที่ใช้จริง

ความเสถียร (stability) — อัลกอริทึมจัดเรียงจะ เสถียร ก็ต่อเมื่อ ค่าที่เท่ากันยังคงลำดับเดิมเทียบกันหลังจัดเรียงเสร็จ

ทำไมต้องสนใจ? สมมติเรียงรายชื่อพนักงานตามชื่อไว้ก่อน แล้วเรียงอีกครั้งตามแผนก ถ้าอัลกอริทึม เสถียร คนในแผนกเดียวกันจะยังเรียงตามชื่ออยู่ — เราจึง “ซ้อนการเรียง” หลายชั้นได้ ถ้าไม่เสถียร ลำดับชื่อเดิมจะปั่นป่วน

จัดเรียงแบบ O(n²): บับเบิล เลือก และแทรก

สามอัลกอริทึมนี้คือการจัดเรียง “แบบตรงไปตรงมา” — แบบที่คุณอาจคิดเองได้ก่อนเรียนอะไรที่ฉลาดกว่านี้ ทั้งสามตัวเปรียบเทียบค่าที่อยู่ติดกันหรือใกล้กัน และในกรณีเลวร้ายต้องเปรียบเทียบราว n²/2 ครั้ง ความต่างอยู่ที่ วิธีย้ายข้อมูล และที่สำคัญคือ ตัวไหนรักษาความเสถียรได้บ้าง

Bubble sort

ไล่สแกนอาร์เรย์ซ้ำ ๆ แล้วสลับคู่ที่อยู่ติดกันหากลำดับผิด แต่ละรอบ (pass) จะ “ดัน” ค่าที่มากที่สุดในส่วนที่เหลือไปอยู่ตำแหน่งท้ายสุดของมัน

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):     # ตัวท้าย i ตัวเรียงเสร็จแล้ว ไม่ต้องแตะ
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:                # ออกก่อนเวลา: รอบนี้ไม่มีการสลับเลย
            break
    return arr

เพราะจะสลับก็ต่อเมื่อ arr[j] > arr[j+1] (มากกว่าจริง ๆ) ค่าที่ เท่ากัน จึงไม่มีวันถูกสลับข้ามกัน — bubble sort จึง เสถียร

ไล่ตามมือบนอาร์เรย์ [5, 3, 8, 4, 2]:

รอบ	การเปรียบเทียบ (สลับไหม?)	อาร์เรย์หลังรอบนี้	จำนวนสลับ
1	(5,3)✓ (5,8)✗ (8,4)✓ (8,2)✓	[3, 5, 4, 2, 8]	3
2	(3,5)✗ (5,4)✓ (5,2)✓	[3, 4, 2, 5, 8]	2
3	(3,4)✗ (4,2)✓	[3, 2, 4, 5, 8]	1
4	(3,2)✓	[2, 3, 4, 5, 8]	1

เรียงเสร็จหลัง ๔ รอบ รวมสลับ ๗ ครั้ง รอบที่ ๕ จะไม่มีการสลับเลย ยืนยันว่าเสร็จแล้ว — การเช็ก “ไม่มีการสลับ” นี้เองที่ทำให้ bubble sort กรณีดีสุด (ข้อมูลเรียงมาแล้ว) เป็น O(n)

Selection sort

หา ค่าน้อยที่สุด ในส่วนที่ยังไม่เรียง แล้วสลับมันมาไว้ตำแหน่งหน้าสุด ทำซ้ำกับส่วนที่เหลือ

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # สลับแค่ครั้งเดียวต่อรอบ
    return arr

selection sort จะสแกน ทั้งหมด ของส่วนที่ยังไม่เรียงเพื่อหาค่าน้อยสุดเสมอ ไม่ว่าข้อมูลจะเรียงมาดีแค่ไหน จึงไม่มี “ออกก่อนเวลา” แบบ bubble sort และเป็น O(n²) แม้แต่กรณีดีสุด

ที่แย่กว่านั้นคือ การสลับครั้งเดียวท้ายแต่ละรอบสามารถ “กระโดดข้าม” ค่าที่เท่ากันไปได้ selection sort จึง ไม่เสถียร ตัวอย่าง: จัดเรียงตามตัวเลข โดยเก็บตัวอักษรไว้เป็นแท็กบอกตัวตนเดิม

[(5,A), (3,B), (5,C), (1,D)] → ค่าน้อยสุดคือ (1,D) ที่ดัชนี 3 สลับกับดัชนี 0: [(1,D), (3,B), (5,C), (5,A)] — สังเกตว่า (5,C) ตอนนี้อยู่ ก่อน (5,A) ทั้งที่เดิม A อยู่ก่อน C ในอาร์เรย์ตั้งต้น ลำดับสัมพัทธ์ของค่าที่เท่ากันถูกสลับ

Insertion sort

สร้าง “ส่วนที่เรียงแล้ว” ทีละตัวจากซ้ายไปขวา: หยิบตัวถัดไป แล้วเลื่อนมันไปทางซ้ายผ่านทุกตัวที่มากกว่าในส่วนที่เรียงแล้ว จากนั้นวางมันลงในช่องที่ถูกต้อง

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:   # ต้องมากกว่าจริง ๆ ถึงจะเลื่อน (กันเสียเสถียรภาพ)
            arr[j + 1] = arr[j]          # เลื่อนตัวที่มากกว่าไปทางขวา
            j -= 1
        arr[j + 1] = key                 # วาง key ลงในช่องว่าง
    return arr

เงื่อนไข while ใช้ arr[j] > key (มากกว่าจริง ๆ) ค่าที่เท่ากันจึงไม่มีวันถูกเลื่อนข้าม key ไป — insertion sort จึง เสถียร และยังเร็วที่สุดในสามตัวนี้เมื่อข้อมูล เกือบเรียงอยู่แล้ว เพราะแต่ละตัวเลื่อนแค่เท่าที่จำเป็นจริง ๆ กรณีดีสุดจึงเป็น O(n)

จัดเรียงแบบ O(n log n): แบ่งแยกและเอาชนะ

ทั้งสองอัลกอริทึมด้านล่างเอาชนะ O(n²) ได้ด้วยกลเม็ดเดียวกัน: แบ่งแยกและเอาชนะ (divide and conquer) — แบ่งปัญหาเป็นชิ้นเล็กลง แก้แต่ละชิ้นแบบเวียนเกิด (recursive) แล้วรวมผลลัพธ์ ความลึกของการเวียนเกิดคือ log n (ตัดครึ่งทุกครั้ง) และแต่ละชั้นของการเวียนเกิดทำงานรวม O(n) จึงได้ O(n log n)

Merge sort — แบ่งก่อน แล้วค่อยผสาน

แบ่งรายการครึ่งหนึ่งไปเรื่อย ๆ แบบเวียนเกิดจนเหลือตัวเดียว (ถือว่า “เรียงแล้ว” โดยปริยาย) แล้ว ผสาน (merge) ครึ่งที่เรียงแล้วกลับเข้าด้วยกัน โดยหยิบค่าหน้าสุดที่น้อยกว่าออกมาทีละตัว

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])       # แบ่ง
    right = merge_sort(arr[mid:])      # แบ่ง
    return merge(left, right)          # ผสาน

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= (ไม่ใช่ <) ให้ฝั่งซ้ายชนะเมื่อเท่ากัน: เสถียร
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])            # เก็บที่เหลือของฝั่งซ้าย
    result.extend(right[j:])
    return result

แบ่งครึ่ง [8, 3, 7, 4, 2, 6, 1, 5] ไปเรื่อย ๆ:

[8,3,7,4,2,6,1,5]
[8,3,7,4]        [2,6,1,5]
[8,3]  [7,4]     [2,6]  [1,5]
[8][3] [7][4]    [2][6] [1][5]     <- กรณีฐาน: เหลือตัวเดียว
[3,8]  [4,7]     [2,6]  [1,5]      <- ผสานเป็นคู่
   [3,4,7,8]        [1,2,5,6]      <- ผสานเป็นสี่ตัว
      [1,2,3,4,5,6,7,8]            <- ผสานครั้งสุดท้าย

merge sort เป็น O(n log n) ทั้งกรณี ดีสุด เฉลี่ย และเลวร้ายสุด — ไม่มีข้อมูลอินพุตแบบไหนทำให้มันช้าลงได้ — และ เสถียร เพราะ merge เลือกจากฝั่งซ้ายเมื่อค่าเท่ากัน ต้นทุนคือ list result ต้องใช้หน่วยความจำเพิ่ม O(n) (ไม่ใช่ in-place)

Quicksort — แบ่งกั้น แล้วเวียนเกิด

เลือก ตัวหลัก (pivot) แล้วจัดอาร์เรย์ใหม่ให้ทุกตัวที่ <= pivot อยู่ก่อนมัน และทุกตัวที่มากกว่าอยู่หลังมัน (เรียกว่า partitioning) จากนั้นเวียนเกิดจัดเรียงแต่ละฝั่ง ต่างจาก merge sort ตรงที่ขั้นตอนรวมผลลัพธ์แทบไม่มีต้นทุน — พอสองฝั่งเรียงเสร็จ อาร์เรย์ทั้งหมดก็เรียงเสร็จทันที

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)      # เวียนเกิดฝั่งซ้ายของ pivot
        quicksort(arr, p + 1, hi)      # เวียนเกิดฝั่งขวาของ pivot

def partition(arr, lo, hi):
    pivot = arr[hi]                    # ใช้ตัวท้ายเป็น pivot (ง่าย แต่เสี่ยงที่สุด)
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1                       # ดัชนีที่ pivot ไปอยู่จริง

quicksort โดยเฉลี่ยเป็น O(n log n) และเพราะทำงานแบบ in-place ด้วยค่าคงที่ (constant) ที่เล็ก จึง เร็วกว่าในทางปฏิบัติ กว่า merge sort บ่อยครั้ง แต่กรณีเลวร้ายสุดคือ O(n²): ถ้า pivot เป็นค่าน้อยสุดหรือมากสุดของส่วนที่เหลือเสมอ การแบ่งกั้นจะแยก n ตัวเป็นกลุ่ม n-1 กับ 0 — ไม่ต่างจากไม่ได้แบ่งเลย อาร์เรย์ที่เรียงมาแล้วพร้อมกับใช้ pivot เป็น “ตัวท้าย” คือกรณีเลวร้ายสุดนี้เป๊ะ ๆ การสลับข้างในเวอร์ชัน partition ยังจัดลำดับค่าที่เท่ากันใหม่แบบไม่แน่นอน quicksort จึงโดยทั่วไป ไม่เสถียร (การสุ่มเลือก pivot หรือเลือกค่ามัธยฐานจากสามตัวเลือก ช่วยให้กรณีเลวร้ายสุด O(n²) แทบไม่เกิดในทางปฏิบัติ — แต่ไม่มีทางเป็นไปไม่ได้เลยด้วยโครงสร้างของอัลกอริทึมเอง)

ขีดจำกัดล่างของ O(n log n) — ทำไมทำได้ดีกว่านี้ไม่ได้

พิสูจน์ได้จริง ไม่ใช่แค่สังเกตเห็น ว่าอัลกอริทึมใดก็ตามที่จัดเรียงด้วยการเปรียบเทียบคู่ค่าล้วน ๆ ต้องใช้การเปรียบเทียบอย่างน้อย Ω(n log n) ครั้งในกรณีเลวร้ายสุด แนวคิดคือ decision tree (ต้นไม้การตัดสินใจ):

• comparison sort ใด ๆ ที่รันบนข้อมูล n ตัวที่แตกต่างกัน ต้องสามารถสร้างผลลัพธ์เป็นได้ทุกหนึ่งใน n! ลำดับที่เป็นไปได้
• แต่ละการเปรียบเทียบมีแค่สองผลลัพธ์ (< หรือ >) จึงมองอัลกอริทึมเป็นต้นไม้ไบนารีของการเปรียบเทียบ: ใบแต่ละใบตรงกับลำดับผลลัพธ์สุดท้ายหนึ่งแบบ
• เพื่อแยกแยะ n! ลำดับที่ต่างกันได้ ต้นไม้ต้องมีใบอย่างน้อย n! ใบ ความลึกของต้นไม้ — จำนวนการเปรียบเทียบกรณีเลวร้ายสุด — จึงต้องอย่างน้อย log₂(n!)
• ตามการประมาณของ Stirling log₂(n!) = Ω(n log n)

ตัวอย่างเล็ก: สำหรับ n = 3 ตัว มี 3! = 6 ลำดับที่เป็นไปได้ ต้นไม้ตัดสินใจแบบไบนารีต้องมี ⌈log₂ 6⌉ = 3 ระดับจึงจะมีใบที่แยกแยะได้ครบ ๖ ใบ — ดังนั้น comparison sort ที่ถูกต้อง ใด ๆ ต้องใช้การเปรียบเทียบสูงสุดถึง ๓ ครั้งเพื่อจัดเรียง ๓ ตัว ไม่ว่าจะเขียนฉลาดแค่ไหน นี่คือเหตุผลที่ merge sort และ quicksort ที่ O(n log n) ถือว่าเหมาะสมที่สุดในบรรดา comparison sort แล้ว — คุณไม่มีทางคิดค้น comparison sort ที่เร็วกว่านี้ในเชิงเส้นกำกับ (asymptotic) ได้ (แต่อัลกอริทึมที่ไม่เปรียบเทียบค่า เช่น counting sort หรือ radix sort เอาชนะ O(n log n) ได้ — เพราะอาศัยโครงสร้างพิเศษเพิ่มเติม เช่น คีย์เป็นจำนวนเต็มที่มีขอบเขตจำกัด แทนที่จะเปรียบเทียบค่า)

ทำไมความเสถียรถึงสำคัญในทางปฏิบัติ

ความเสถียรฟังดูเป็นเรื่องวิชาการ จนกว่าคุณจะต้องเรียงข้อมูลด้วยมากกว่าหนึ่งคีย์ สมมติมีรายการคำสั่งซื้อ อยากเรียงตาม region ก่อน แล้ว ภายในแต่ละภูมิภาค เรียงตาม order_date:

orders = [
    {"region": "West", "date": "2024-03-01"},
    {"region": "East", "date": "2024-01-15"},
    {"region": "West", "date": "2024-01-20"},
    {"region": "East", "date": "2024-02-10"},
]

# เรียงคีย์รองก่อน แล้วค่อยเรียงคีย์หลักทีหลัง
# ถ้าอัลกอริทึมเสถียร ลำดับวันที่ภายในแต่ละภูมิภาคจะยังคงอยู่
orders.sort(key=lambda o: o["date"])     # เรียงครั้งที่ 1: ตามวันที่
orders.sort(key=lambda o: o["region"])   # เรียงครั้งที่ 2: ตามภูมิภาค (เสถียร! วันที่ยังเรียงอยู่)

เทคนิค “เรียงสองรอบ” นี้ใช้ได้เพราะ sort() ของ Python รับประกันว่าเสถียร ถ้าใช้อัลกอริทึมที่ไม่เสถียร (เช่น quicksort หรือ selection sort แบบไร้เดียงสา) เรียงรอบที่สอง ลำดับวันที่ภายในแต่ละภูมิภาคอาจปั่นป่วนได้ — บั๊กแบบแนบเนียนที่โผล่มาก็ต่อเมื่อมีคีย์ซ้ำกัน ซึ่งเป็นสิ่งที่ข้อมูลจริงเจอตลอดเวลา (คำสั่งซื้อหลายรายการมักอยู่ภูมิภาคเดียวกัน)

Timsort — สิ่งที่ sorted() รันจริง ๆ

sorted() และ list.sort() ของ Python (รวมถึง Arrays.sort() ของ Java สำหรับ object) ไม่ได้ใช้ merge sort หรือ quicksort แบบตำราตรง ๆ — แต่ใช้ Timsort อัลกอริทึมลูกผสมที่ Tim Peters ออกแบบมาเพื่อใช้ประโยชน์จากรูปแบบของข้อมูลจริงโดยเฉพาะ:

• สแกนหา run ที่มีอยู่แล้ว — ช่วงต่อเนื่องที่เรียงขึ้นหรือลงอยู่แล้วในข้อมูล (ข้อมูลจริงแทบไม่เคยสุ่มล้วน ๆ มักมีลำดับบางส่วนอยู่แล้ว) — แล้วกลับด้าน run ที่เรียงลงให้เรียงขึ้นทันที
• run สั้น ๆ (ต่ำกว่าเกณฑ์ ปกติ ๓๒–๖๔ ตัว) จะถูกขยายและเรียงด้วย insertion sort — ซึ่งเร็วมากบนข้อมูลขนาดเล็กหรือเกือบเรียงแล้ว
• run ที่ยาวกว่าจะถูกรวมด้วยการ ผสาน แบบ merge sort อย่างพิถีพิถัน
• ผลลัพธ์: กรณีดีสุดเป็น O(n) (เช่น ข้อมูลเรียงมาแล้วหรือเรียงกลับด้านอยู่แล้ว) กรณีเฉลี่ยและเลวร้ายสุดเป็น O(n log n) และที่สำคัญคือ รับประกันความเสถียร ซึ่งเป็นเหตุผลที่แพทเทิร์น “เรียงสองรอบ” ด้านบนเชื่อถือได้

ข้อคิดเชิงปฏิบัติ: อย่าเขียน bubble/selection/insertion sort เองเพื่อใช้จัดเรียงข้อมูลจริงในโปรดักชัน ใช้ตัวจัดเรียงในตัวของภาษา (Timsort ใน Python/Java, Introsort ใน C++/std::sort) — เพราะทั้งเหมาะสมที่สุดเชิงเส้นกำกับ และผ่านการทดสอบกับ edge case ที่คุณอาจนึกไม่ถึงมาแล้ว

ความซับซ้อน

อัลกอริทึม	ดีสุด (best)	เฉลี่ย (avg)	เลวร้าย (worst)	หน่วยความจำ	เสถียร?
Linear search	O(1)	O(n)	O(n)	O(1)	—
Binary search	O(1)	O(log n)	O(log n)	O(1)	—
Bubble sort	O(n)	O(n²)	O(n²)	O(1)	ใช่
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	ไม่
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	ใช่
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	ใช่
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	ไม่
Timsort (sorted())	O(n)	O(n log n)	O(n log n)	O(n)	ใช่

binary search กรณีดีสุดเป็น O(1) เมื่อเจอที่ค่ากลางทันที ส่วน selection sort กรณีดีสุด ยังคง เป็น O(n²) — เพราะมันสแกนส่วนที่เหลือทั้งหมดเพื่อหาค่าน้อยสุดเสมอ ต่างจาก bubble/insertion sort ที่ออกก่อนเวลาได้เมื่อข้อมูลเรียงมาแล้ว

โจทย์จากโลกจริง

ลองนึกถึงแอประบบสมาชิกที่มีผู้ใช้ ๕๐ ล้านคน เก็บเรียงตาม user_id ไว้ในไฟล์ดัชนี เมื่อมีคนล็อกอิน เราต้องค้นหา user_id ของเขา

ถ้าใช้ linear scan ไล่ทีละแถว กรณีเลวร้ายต้องอ่าน ๕๐ ล้านแถวต่อการล็อกอินหนึ่งครั้ง — ช้าจนใช้งานจริงไม่ได้เมื่อมีคนล็อกอินพร้อมกันมาก ๆ

ถ้าใช้ binary search บนข้อมูลที่เรียงแล้ว ใช้เพียงราว log₂(50,000,000) ≈ 26 ก้าว ก็ตอบได้ — เร็วกว่าหลายล้านเท่า

เมื่อใดการเรียงก่อนถึงคุ้ม? การเรียงข้อมูลครั้งแรกมีต้นทุน O(n log n) แต่ถ้าหลังจากนั้นต้องค้นหาซ้ำ ๆ หลายครั้ง (k ครั้ง) ต้นทุนรวมจะเป็น O(n log n + k log n) ซึ่งคุ้มกว่าค้นหาเชิงเส้น O(k·n) มาก เมื่อ k ใหญ่ — แต่ถ้าค้นหาแค่ครั้งเดียวแล้วเลิก linear scan O(n) อาจคุ้มกว่าการเสียเวลาเรียงทั้งกอง

แบบฝึกหัด

๑. ไล่ตามมือ: binary search จากอาร์เรย์ [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] ค้นหา target = 13 ให้เขียนค่าของ lo, mid, hi ในแต่ละรอบจนเจอ

เฉลย

รอบ	lo	hi	mid	arr[mid]	ทำอะไร
1	0	9	4	9	9 < 13 → lo = 5
2	5	9	7	15	15 > 13 → hi = 6
3	5	6	5	11	11 < 13 → lo = 6
4	6	6	6	13	เจอ! คืนดัชนี 6

ใช้เพียง ๔ รอบเทียบกับการไล่เชิงเส้นที่ต้องดูถึงตัวที่ ๗

๒. หาตำแหน่งแรกและตำแหน่งสุดท้าย ถ้าอาร์เรย์มีค่าซ้ำได้ เช่น [2, 4, 4, 4, 6, 8] แล้วต้องการหา ดัชนีแรกสุด ที่มีค่า 4 จะแก้ binary search อย่างไร?

เฉลย

เมื่อเจอ arr[mid] == target อย่ารีบคืนค่า ให้ “จำดัชนีไว้แล้วเดินต่อไปทางซ้าย” เพื่อหาตัวที่อยู่ก่อนหน้า:

def first_occurrence(arr, target):
    lo, hi = 0, len(arr) - 1
    ans = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            ans = mid        # จำไว้ แล้วลองหาทางซ้ายต่อ
            hi = mid - 1
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

หาตำแหน่งสุดท้ายทำกลับกัน: เมื่อเจอให้ lo = mid + 1 เพื่อเดินไปทางขวา

๓. ทำไมต้องเรียงก่อน อธิบายว่าทำไม binary search จึงใช้กับข้อมูลที่ “ยังไม่เรียง” ไม่ได้ ยกตัวอย่างประกอบ

เฉลย

binary search ตัดสินใจว่าจะไปซ้ายหรือขวาจากกฎ “ถ้าค่ากลางน้อยกว่า target คำตอบต้องอยู่ขวา” ซึ่งกฎนี้เป็นจริง ก็ต่อเมื่อข้อมูลเรียงลำดับแล้ว เท่านั้น

ตัวอย่าง: ใน [9, 1, 5, 3, 7] หา 7 ค่ากลางคือ 5 เนื่องจาก 5 < 7 เราจึงทิ้งครึ่งซ้ายและไปดูครึ่งขวา [3, 7] — บังเอิญเจอ แต่ถ้าหา 1 ค่ากลาง 5 > 1 เราจะทิ้งครึ่งขวาและไปครึ่งซ้าย [9] แล้วสรุปผิดว่า “ไม่มี 1” ทั้งที่ 1 อยู่ในรายการ การตัดทิ้งครึ่งหนึ่งจึงเชื่อถือได้เฉพาะกับข้อมูลที่เรียงแล้ว

๔. จับ off-by-one โค้ดนี้ผิดตรงไหน?

def search(arr, target):
    lo, hi = 0, len(arr)        # (ก)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid            # (ข)
        else:
            hi = mid
    return -1

เฉลย

บรรทัด (ข) ผิด: lo = mid ทำให้ lo ไม่ขยับเมื่อช่วงแคบลงเหลือ ๒ ตัว (เพราะ mid จะเท่ากับ lo) → วนไม่รู้จบ ต้องแก้เป็น lo = mid + 1

(หมายเหตุ: รูปแบบ hi = len(arr) คู่กับ while lo < hi และ hi = mid เป็นสไตล์ half-open ที่ถูกต้องได้ ตราบใดที่ฝั่ง lo ใช้ mid + 1 เสมอ)

๕. นับจำนวนก้าวของ binary search อาร์เรย์มี ๑,๐๐๐,๐๐๐ ตัว binary search ใช้ก้าวมากสุดกี่ก้าวในกรณีเลวร้าย?

เฉลย

ประมาณ ⌈log₂(1,000,000)⌉ = 20 ก้าว เพราะแต่ละก้าวตัดข้อมูลครึ่งหนึ่ง 2²⁰ = 1,048,576 > 1,000,000 เทียบกับ linear search ที่อาจต้องดูถึง ๑,๐๐๐,๐๐๐ ครั้ง

๖. ไล่ตามมือ: bubble sort ไล่ตามมือ bubble sort บนอาร์เรย์ [5, 3, 8, 4, 2] แต่ละรอบให้ระบุการเปรียบเทียบ ตัวไหนสลับบ้าง และอาร์เรย์ที่ได้ รวมแล้วมีการสลับกี่ครั้ง?

เฉลย

รอบ	การเปรียบเทียบ (สลับไหม?)	อาร์เรย์หลังรอบนี้
1	(5,3)✓ (5,8)✗ (8,4)✓ (8,2)✓	[3, 5, 4, 2, 8]
2	(3,5)✗ (5,4)✓ (5,2)✓	[3, 4, 2, 5, 8]
3	(3,4)✗ (4,2)✓	[3, 2, 4, 5, 8]
4	(3,2)✓	[2, 3, 4, 5, 8]

รวมสลับ: 3 + 2 + 1 + 1 = ๗ ครั้ง ใน ๔ รอบ รอบที่ ๕ จะไม่มีการสลับเลย ยืนยันว่าเรียงเสร็จแล้ว

๗. selection sort ทำลายความเสถียร เรียง [(5,'A'), (3,'B'), (5,'C'), (1,'D')] ตามค่าตัวเลขด้วย selection sort พร้อมไล่ตามการสลับ ลำดับสุดท้ายของ 5 สองตัวยังตรงกับลำดับสัมพัทธ์เดิมหรือไม่?

เฉลย

รอบ 1: ค่าน้อยสุดของทั้งอาร์เรย์คือ (1,'D') ที่ดัชนี 3 สลับกับดัชนี 0 → [(1,'D'), (3,'B'), (5,'C'), (5,'A')]

รอบ 2: ค่าน้อยสุดของ [(3,'B'), (5,'C'), (5,'A')] คือ (3,'B') อยู่ตำแหน่งเดิมแล้ว — ไม่สลับ

รอบ 3: ค่าน้อยสุดของ [(5,'C'), (5,'A')] คือ (5,'C') (ซ้ายสุดเมื่อเท่ากัน) อยู่ตำแหน่งเดิมแล้ว — ไม่สลับ

ผลลัพธ์สุดท้าย: [(1,'D'), (3,'B'), (5,'C'), (5,'A')] เดิม A อยู่ก่อน C แต่ตอนนี้ C อยู่ก่อน A ลำดับสลับกัน → selection sort ไม่เสถียร

๘. กรณีดีสุดของ insertion sort ไล่ตามมือ insertion sort บนอาร์เรย์ที่เกือบเรียงแล้ว [1, 2, 4, 3, 5] นับจำนวนการเลื่อนตัว (shift) ทั้งหมด แล้วอธิบายว่าทำไมนี่จึงใกล้เคียงกรณีดีสุด O(n) ของ insertion sort มากกว่ากรณีเลวร้ายสุด O(n²)

เฉลย

• i=1, key=2: เทียบกับ 1 (ไม่มากกว่า) → เลื่อน 0 ครั้ง
• i=2, key=4: เทียบกับ 2 (ไม่มากกว่า) → เลื่อน 0 ครั้ง
• i=3, key=3: เทียบกับ 4 (มากกว่า เลื่อน) → เลื่อน 1 ครั้ง จากนั้นเทียบกับ 2 (ไม่มากกว่า) → หยุด วาง 3
• i=4, key=5: เทียบกับ 4 (ไม่มากกว่า) → เลื่อน 0 ครั้ง

รวม: เลื่อน ๑ ครั้ง เพราะอาร์เรย์เกือบเรียงอยู่แล้ว ตัวส่วนใหญ่จึงแค่เทียบครั้งเดียวก็รู้ว่าอยู่ถูกที่แล้ว ลูป while ด้านในของ insertion sort แทบไม่ทำงาน ถ้าเป็นอาร์เรย์ที่เรียงกลับด้าน (reverse-sorted) ทุกตัวจะต้องเลื่อนไปจนสุดหน้า กลายเป็นกรณีเลวร้ายสุด O(n²) เต็มรูปแบบ

๙. กรณีเลวร้ายสุดของ quicksort โค้ด quicksort/partition ด้านบนเลือก arr[hi] (ตัวท้าย) เป็น pivot เสมอ ถ้ารันบนอาร์เรย์ที่เรียงมาแล้ว [1, 2, 3, 4, 5] จะเกิดอะไรขึ้น? ความซับซ้อนด้านเวลาคืออะไร และทำไม?

เฉลย

บนอาร์เรย์ที่เรียงแล้ว arr[hi] จะเป็นค่า มากที่สุด ของส่วนที่เหลือเสมอ การแบ่งกั้นแต่ละครั้งจึงเอาทุกตัวไปไว้ฝั่ง “น้อยกว่า” และไม่มีตัวไหนอยู่ฝั่ง “มากกว่า” เลย — การแบ่งจึงเป็น n-1 กับ 0 ทุกครั้ง แทนที่จะเป็นประมาณ n/2 กับ n/2 นั่นแปลว่าการเวียนเกิดไม่ได้ตัดครึ่งปัญหา แต่ลดลงแค่ทีละหนึ่งตัวต่อการเรียก ทำให้มีการเวียนเกิด n ชั้นแทนที่จะเป็น log n แต่ละชั้นทำงาน O(n) → รวม O(n²) วิธีแก้ในทางปฏิบัติ: เลือก pivot แบบสุ่ม หรือเลือกค่ามัธยฐานของตัวแรก/กลาง/ท้าย เพื่อไม่ให้อินพุตที่เรียงมาแล้ว (หรือถูกออกแบบมาโจมตี) กระตุ้นกรณีเลวร้ายสุดได้อย่างแน่นอน

๑๐. ทายผลลัพธ์: ความเสถียรในการเรียงสองรอบ

students = [
    {"name": "Anan", "grade": "B"},
    {"name": "Beau", "grade": "A"},
    {"name": "Cham", "grade": "B"},
    {"name": "Dara", "grade": "A"},
]
students.sort(key=lambda s: s["name"])
students.sort(key=lambda s: s["grade"])
print([s["name"] for s in students])

ผลลัพธ์คืออะไร และคำตอบจะเปลี่ยนไปหรือไม่ถ้า sort() ไม่เสถียร?

เฉลย

พิมพ์ ['Beau', 'Dara', 'Anan', 'Cham']

เรียงตามชื่อก่อนได้ [Anan, Beau, Cham, Dara] การเรียงครั้งที่สองตามเกรดจะจัดกลุ่ม A (Beau, Dara) ไว้ก่อนกลุ่ม B (Anan, Cham) — และเพราะ sort() ของ Python เสถียร แต่ละกลุ่มจึง ยังคง ลำดับตัวอักษรเดิมจากการเรียงครั้งแรกไว้ ถ้า sort() ไม่เสถียร ลำดับภายในกลุ่ม A และกลุ่ม B อาจออกมาแบบไหนก็ได้ (เช่น [Dara, Beau, Cham, Anan]) — การรับประกันว่า “เรียงตามตัวอักษรภายในแต่ละเกรด” จะหายไป

วิพากษ์โค้ดจากปัญญาประดิษฐ์

ขอให้ AI เขียน binary search ให้ ได้โค้ดนี้มาพร้อมคำรับรองว่า “ทดสอบแล้ว ทำงานถูกต้องแน่นอน”

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid          # <-- ดูบรรทัดนี้
        else:
            hi = mid          # <-- และบรรทัดนี้
    return -1

โจทย์: รันด้วย binary_search([1, 2, 3], 2) ดู — มันจะ ค้างไม่จบ ให้หาว่าผิดตรงไหนและแก้

เฉลย

บั๊กคือ lo = mid และ hi = mid ที่ ไม่มี +1/-1 ทำให้ช่วงไม่หดเมื่อเหลือข้อมูล ๒ ตัว

ลองไล่ binary_search([1, 2, 3], 0): เริ่ม lo=0, hi=2, mid=1, arr[1]=2 > 0 → hi = 1; รอบต่อมา lo=0, hi=1, mid=0, arr[0]=1 > 0 → hi = 0; ตอนนี้ lo=0, hi=0, mid=0, arr[0]=1 > 0 → hi = 0 ค่าเดิมไม่ขยับ วนซ้ำชั่วนิรันดร์

แก้โดยเลื่อนขอบเขตให้ข้าม mid เสมอ:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1      # แก้แล้ว
        else:
            hi = mid - 1      # แก้แล้ว
    return -1

บทเรียน: โค้ดจาก AI ที่ “ดูเหมือนถูก” อาจมี off-by-one ซ่อนอยู่ ต้องทดสอบด้วยกรณีขอบ (เช่นค่าที่ไม่มีในรายการ) เสมอ

คำสั่งที่สอง: “เขียนฟังก์ชันจัดเรียงที่เสถียร” AI ตอบกลับมาด้วย selection sort พร้อมป้ายกำกับอย่างมั่นใจว่าเสถียร

def stable_sort(arr, key=lambda x: x):
    # คอมเมนต์จาก AI: "Selection sort — เรียบง่ายและเสถียร"
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if key(arr[j]) < key(arr[min_idx]):
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

เฉลย

selection sort ไม่เสถียร — ดูตัวอย่างค้านในข้อ ๗ ด้านบนที่คีย์เท่ากันสองตัวถูกสลับลำดับโดยการสลับครั้งสุดท้ายของแต่ละรอบ คอมเมนต์ของ AI ผิดล้วน ๆ — “เรียบง่าย” ไม่ได้แปลว่า “เสถียร” สองคุณสมบัตินี้ไม่เกี่ยวข้องกัน ถ้าต้องการ sort ที่เสถียรจริง ๆ ให้ใช้ sorted()/list.sort() ในตัว (Timsort รับประกันเสถียร) หรือเขียน merge sort โดยใช้ <= ในขั้นตอน merge บทเรียน: ต้องตรวจสอบ คุณสมบัติ ที่อ้างไว้เสมอ (เสถียร, in-place, O(n log n)) เทียบกับกลไกจริงของอัลกอริทึม — อย่าเชื่อคอมเมนต์หรือ docstring ตามที่เขียนไว้เฉย ๆ โดยเฉพาะอันที่ AI เขียนอธิบายโค้ดของตัวเอง

🎮 เกมเดฟ: การค้นหาและการจัดเรียง

ทุก ๆ เฟรม เรนเดอเรอร์ 2D ต้องตัดสินใจว่าจะวาดสไปรต์ที่ซ้อนทับกันตาม ลำดับ ไหน — “อัลกอริทึมของจิตรกร” (painter’s algorithm) แบบคลาสสิกคือวาดของที่อยู่ไกลก่อน แล้ววาดของที่อยู่ใกล้ทับลงไปทีหลัง ซึ่งไม่ใช่อะไรอื่นนอกจากการจัดเรียงสไปรต์ตามความลึก (y หรือ z-index เฉพาะ) ก่อนวาด สไปรต์ขยับแค่ไม่กี่พิกเซลต่อเฟรม ลำดับของเฟรมก่อนหน้าจึงเกือบเรียงอยู่แล้ว — นี่คือกรณีที่ insertion sort ถูกออกแบบมาให้เหมาะเป๊ะ และเมื่อมีรายการที่เรียงแล้วอยู่ในมือ — ไม่ว่าจะเป็นเวลาสปอว์นหรือตารางคะแนนสูงสุด — binary search จะเปลี่ยน “หาอีเวนต์ถัดไป” จากการสแกน O(n) ให้เป็นการค้นหา O(log n)

จัดเรียงสไปรต์ตามความลึก: อัลกอริทึมของจิตรกร

class Sprite:
    def __init__(self, name, y, spawn_order):
        self.name = name
        self.y = y                      # คีย์ความลึก: y มากกว่า = ใกล้กล้องมากกว่า
        self.spawn_order = spawn_order  # ตัวตัดสินเสมอ: สไปรต์ไหนถูกสร้างก่อน

# ร่างแรกแบบไร้เดียงสา: เรียงตาม y แล้วหวังว่าจะไม่มีปัญหา
def naive_depth_sort(sprites):
    return sorted(sprites, key=lambda s: s.y)

ดูเหมือนจะโอเค — จนกว่าสไปรต์สองตัวจะมี y เท่ากัน (คบเพลิงกับลายพื้นบนไทล์เดียวกัน) sorted() ของ Python เสถียร (Timsort) ดังนั้น ภายในเฟรมเดียว สไปรต์ที่เท่ากันจะคงลำดับตามรายการอินพุตไว้ แต่ถ้า sprites ถูกสร้างใหม่ระหว่างเฟรม (ศัตรูตายแล้วถูกลบออก รายการถูกกรอง) ลำดับ อินพุต ของคู่ที่เท่ากันก็เปลี่ยนได้เช่นกัน — ลำดับการวาดจึงพลิกกลับแบบเงียบ ๆ และลายพื้นตัวหนึ่งกะพริบขึ้นมาทับอีกตัวในเฟรมนั้น ทั้งที่ไม่มีตัวไหนขยับเลย ทางแก้ที่ขยายผลได้คือใส่ตัวตัดสินเสมออย่างชัดเจน เพื่อให้สไปรต์ที่ความลึกเท่ากันได้ผลลัพธ์แบบเดิมเสมอ ไม่ว่าลำดับรายการจะบังเอิญเป็นอย่างไร:

def stable_depth_sort(sprites):
    # ตัวตัดสินเสมอชัดเจน: y เท่ากัน -> สไปรต์ที่มีอยู่ก่อนวาดก่อน
    return sorted(sprites, key=lambda s: (s.y, s.spawn_order))

เพราะสไปรต์ขยับแค่นิดเดียวต่อเฟรม รายการที่เรียงไว้เมื่อเฟรมก่อนจึง เกือบเรียงอยู่แล้ว ในเฟรมนี้ — มีแค่ไม่กี่ตัวที่ต้องขยับ นี่คืออินพุตที่ insertion sort เร็วที่สุดพอดี:

def insertion_depth_sort(sprites):
    for i in range(1, len(sprites)):
        current = sprites[i]
        key = (current.y, current.spawn_order)
        j = i - 1
        while j >= 0 and (sprites[j].y, sprites[j].spawn_order) > key:
            sprites[j + 1] = sprites[j]
            j -= 1
        sprites[j + 1] = current
    return sprites

บนเฟรมที่เกือบเรียงแล้ว โค้ดนี้ทำงานใกล้เคียงกรณีดีสุด O(n) ของ insertion sort — ถูกกว่าการเรียงใหม่จากศูนย์ด้วยอัลกอริทึมทั่วไป O(n log n) มาก เมื่อจำนวนสไปรต์มากขึ้น

y=70 B

y=100 (วาดทีหลังสุด ใกล้สุด) C

รูป: สไปรต์ A (y=40), B (y=70), C (y=100) ถูกวาดจากไกลไปใกล้ตามลำดับ y จากน้อยไปมาก — แต่ละตัวที่วาดทีหลังจะซ้อนทับตัวก่อนหน้า เหมือนจิตรกรลงสีทีละชั้น

binary search บนตารางเวลาสปอว์นที่เรียงแล้ว

เกมแบบเวฟ (wave-based) เก็บอีเวนต์สปอว์นเป็นรายการที่เรียงตามเวลาไว้ เช่น [2, 6, 6, 12, 18, 25, 30, 40] ทุกเฟรมต้องตอบว่า “อีเวนต์ถัดไปหลัง now คืออันไหน” — ถ้าสแกนจากต้นทุกเฟรม พอตารางเวลายาวขึ้นก็จะเสียเวลาโดยเปล่าประโยชน์ binary search หาตัวแรกที่มากกว่า now จริง ๆ ได้:

def next_spawn_index(timeline, now):
    """timeline คือเวลาสปอว์นที่เรียงแล้ว; คืนดัชนีของอีเวนต์แรกที่มากกว่า now จริง ๆ"""
    lo, hi = 0, len(timeline)
    while lo < hi:
        mid = (lo + hi) // 2
        if timeline[mid] <= now:
            lo = mid + 1
        else:
            hi = mid
    return lo

ตารางคะแนนสูงสุดที่เรียงแล้วก็ใช้หลักการเดียวกัน: เมื่อจะหาว่าคะแนนใหม่ควรอยู่อันดับไหน ใช้ binary search หาตำแหน่งที่ควรแทรก แทนที่จะไล่ดูทุกแถว

แบบฝึกหัด

๑. เขียนคีย์สำหรับการจัดเรียง สไปรต์เป็นทูเพิล (name, y): [("torch", 40), ("player", 70), ("floor_a", 55), ("floor_b", 55)] ให้เขียน key= ที่จะส่งให้ sorted() เพื่อจัดเรียงตามความลึกแบบอัลกอริทึมของจิตรกร แล้วอะไรที่เปราะบางถ้าเรียงด้วย y อย่างเดียวเมื่อ floor_a กับ floor_b มีค่าเท่ากัน?

เฉลย

key=lambda s: s[1] เรียงตาม y เพราะ floor_a กับ floor_b เท่ากันที่ y=55 sorted() ที่เสถียรของ Python จะให้ตัวที่ อยู่ก่อนในรายการอินพุต อยู่ก่อนในผลลัพธ์ — ถูกต้องภายในเฟรมเดียว แต่ขึ้นอยู่กับลำดับรายการที่บังเอิญเป็นแบบนั้น ไม่ใช่คุณสมบัติใด ๆ ของสไปรต์เอง ถ้ารายการอินพุตถูกสร้างใหม่หรือถูกกรองระหว่างเฟรม ลำดับที่เท่ากันอาจพลิกกลับได้โดยไม่มีเหตุผลในเกม ตัวตัดสินเสมอแบบ key=lambda s: (s[1], spawn_order) จะทำให้ผลลัพธ์แน่นอนไม่ว่าลำดับรายการจะเป็นอย่างไร

๒. อธิบายอาการกะพริบ ลายพื้นสองอัน คือเงา S (y=50) และแอ่งน้ำ P (y=50) ถูกวาดทุกเฟรมด้วย sorted(sprites, key=lambda s: s.y) — ไม่มีตัวตัดสินเสมอ เฟรมที่ 1 รายการสไปรต์บังเอิญเป็น [S, P] หลังจากศัตรูตัวอื่นตายและรายการถูกสร้างใหม่ เฟรมที่ 2 รายการบังเอิญกลายเป็น [P, S] ทั้งที่ S กับ P ไม่ได้ขยับเลย บนหน้าจอจะเกิดอะไรขึ้นระหว่างสองเฟรมนี้ และการเพิ่ม spawn_order เป็นตัวตัดสินเสมอช่วยแก้ปัญหานี้อย่างไร?

เฉลย

sorted() เสถียรก็จริง แต่ “เสถียร” หมายความแค่ว่าค่าที่เท่ากันคงลำดับของ รายการอินพุตในการเรียกครั้งนั้น ไว้เท่านั้น — ไม่ได้การันตีความสม่ำเสมอข้ามเฟรม เฟรมที่ 1 เรียง [S, P] (เรียงอยู่แล้ว) แล้ววาด S ก่อน P อินพุตของเฟรมที่ 2 กลายเป็น [P, S] แบบเงียบ ๆ การเรียงที่เสถียรจึงคง P ไว้ก่อน S และวาด P ก่อนในรอบนี้ — ลำดับการวาดของลายพื้นสองอันที่ไม่ขยับและความลึกเท่ากันพลิกกลับ ซึ่งบนหน้าจอจะเห็นเป็นอาการกะพริบหรือ z-fight หนึ่งเฟรม การเรียงด้วย key=lambda s: (s.y, s.spawn_order) แทน จะทำให้ลำดับขึ้นอยู่กับคุณสมบัติของสไปรต์เองเท่านั้น ไม่ใช่ลำดับที่บังเอิญมาถึงในรายการของเฟรมนั้น ค่าที่เท่ากันจึงได้ผลลัพธ์เดิมเสมอ

๓. ไล่ตามมือ binary search บนตารางเวลา ใช้ next_spawn_index ด้านบนกับ timeline = [2, 6, 6, 12, 18, 25, 30, 40] และ now = 6 ให้ไล่ค่า lo, hi, mid แต่ละรอบ ผลลัพธ์คือดัชนีอะไร และชี้ไปที่เวลาสปอว์นไหน แล้วทำไมมันข้าม 6 ทั้งสองตัวไป?

เฉลย

รอบ	lo	hi	mid	timeline[mid]	ทำอะไร
1	0	8	4	18	18 > 6 → hi = 4
2	0	4	2	6	6 <= 6 → lo = 3
3	3	4	3	12	12 > 6 → hi = 3

ลูปจบ (lo == hi == 3) คืนดัชนี 3 ซึ่งชี้ไปที่ timeline[3] = 12 ค่า 6 ทั้งสองตัวถูกข้ามเพราะเงื่อนไข timeline[mid] <= now ถือว่าสปอว์นที่กำหนดไว้ พอดีกับ now เป็นอันที่จัดการไปแล้ว ฟังก์ชันจึงคืนอีเวนต์แรกที่มากกว่า now จริง ๆ ตรงกับความหมาย “อันถัดไป” สำหรับนาฬิกาเกมที่เพิ่งเดินผ่าน 6 ไป

๔. insertion sort เทียบกับ sort ในตัว เมื่อเกือบทุกอย่างเรียงอยู่แล้ว สไปรต์ ๒๐๐ ตัวเรียงมาจากเฟรมก่อนแล้ว มีเพียง ๓ ตัวที่ขยับผ่านตัวข้างเคียงไปในเฟรมนี้ เปรียบเทียบการเรียงใหม่ด้วย sorted() ในตัวของ Python (Timsort) กับ insertion_depth_sort ด้านบน ทำไมทั้งสองแบบถึงเร็วในกรณีนี้ และถ้าโหลดด่านใหม่ทำให้รายการสไปรต์ถูกสร้างใหม่แบบสุ่มลำดับ แบบไหนที่ยังคงเร็วอยู่?

เฉลย

ทั้งสองแบบใกล้เคียง O(n) บนอินพุตนี้: Timsort ตรวจพบ run ที่เรียงแล้วยาว ๆ ในสไปรต์ ๑๙๗ ตัวที่ไม่ขยับ แล้วแค่ผสานตัวไม่กี่ตัวที่ขยับเข้าไป ส่วน insertion_depth_sort ก็เลื่อนแค่ไม่กี่ตัวที่อยู่ผิดที่ผ่านตัวข้างเคียง เพราะตัวอื่นทั้งหมดไม่ผ่านเงื่อนไข while ตั้งแต่แรก ทั้งสองแบบทำงานถูกและถูกที่แบบเดียวกัน เพียงผ่านกลไกต่างกัน ความต่างจะเห็นชัดบนอินพุตที่ แย่: ถ้าโหลดด่านใหม่ทำให้รายการสไปรต์ถูกสร้างใหม่แบบสุ่มลำดับ insertion sort จะแย่ลงแบบเงียบ ๆ กลายเป็นกรณีเลวร้ายสุดเต็มรูปแบบ O(n²) (ทุกตัวอาจต้องเลื่อนข้ามทั้งอาร์เรย์) ในขณะที่ Timsort ยังคงรับประกัน O(n log n) ไม่ว่าอินพุตจะปนเปแค่ไหน กฎง่าย ๆ: เขียน insertion sort เองเฉพาะตอนที่การันตีได้ว่า “เกือบเรียงแล้วจากเฟรมสู่เฟรม” เท่านั้น มิฉะนั้นปล่อยให้ sort ในตัวรับความเสี่ยงแทน

โจทย์ท้าทาย

ก. เรียงใหม่เฉพาะสไปรต์ที่ขยับ การเรียงสไปรต์ทั้ง ๑,๐๐๐ ตัวใหม่จากศูนย์ทุกเฟรมเสียเวลาเปล่าเมื่อมีแค่ไม่กี่ตัวที่ขยับเทียบกับตัวข้างเคียง ให้ร่างวิธีอัปเดตรายการที่เรียงตามความลึกไว้แบบค่อยเป็นค่อยไป โดยแตะเฉพาะสไปรต์ที่เปลี่ยน

แนวทาง

ติดตามว่าสไปรต์ตัวไหนขยับในเฟรมนี้ (เซตเล็ก ๆ ที่เป็น “dirty”) สำหรับแต่ละสไปรต์ที่ dirty: ลบมันออกจากรายการที่เรียงไว้ แล้วใช้ bisect.insort แทรกกลับเข้าไปในตำแหน่งที่ถูกต้อง — bisect หาตำแหน่งแทรกด้วย binary search ใน O(log n) แทนการสแกน ต้นทุนต่อสไปรต์ที่ขยับหนึ่งตัวจึงเป็น O(log n) สำหรับการหาตำแหน่ง บวกต้นทุนการเลื่อนตัวอื่นเพื่อเปิดที่ว่าง เทียบกับ O(n log n) ถ้าเรียงทุกตัวใหม่จากศูนย์ สไปรต์ที่ไม่เคยขยับ (ไทล์พื้นหลัง ของประดับตกแต่งที่อยู่นิ่ง) จะไม่ถูกแตะในการเรียงอีกเลยหลังวางตำแหน่งครั้งแรก ข้อควรระวัง: bisect ทำงานถูกต้องก็ต่อเมื่อรายการ เรียงสมบูรณ์อยู่ก่อนและหลัง การเรียกแต่ละครั้ง ดังนั้นการลบและแทรกกลับเข้า Python list ธรรมดายังเสียเวลา O(n) อยู่ดี — ถ้า n ใหญ่มากและมีตัวที่ขยับหลายตัวต่อเฟรม ให้แบ่งสไปรต์เป็นกลุ่มตามแถว/พื้นที่แล้วเรียงใหม่แค่ภายในกลุ่ม หรือใช้โครงสร้างข้อมูลที่ออกแบบมาสำหรับอัปเดตแบบเรียงลำดับทีละน้อย (เช่น sorted skip list หรือโครงสร้างที่รองรับด้วย balanced tree)

ข. หาศัตรูที่ใกล้ที่สุดโดยไม่ต้องสแกนทุกตัว ขีปนาวุธติดตามเป้าหมายต้องหาศัตรูที่ใกล้ผู้เล่นที่สุดจากศัตรู n ตัวทุกเฟรม การสแกนแบบไร้เดียงสาตรวจระยะห่างของศัตรูทุกตัว — O(n) ต่อการค้นหาหนึ่งครั้ง โอเคสำหรับศัตรู ๒๐ ตัว แต่แพงมากถ้ามีศัตรู ๒,๐๐๐ ตัวและขีปนาวุธหลายสิบลูกค้นหาทุกเฟรม ให้ร่างวิธีที่เร็วขึ้นโดยใช้แนวคิด “เรียงครั้งเดียว ค้นหาหลายครั้ง”

แนวทาง

ถ้าศัตรูขยับช้าเมื่อเทียบกับความถี่ในการค้นหา ให้เก็บดัชนีที่เรียงตามแกนใดแกนหนึ่ง (สมมติ x) ไว้ เมื่อจะหาศัตรูที่ใกล้ตำแหน่ง x ของผู้เล่นที่สุด ใช้ binary search (bisect) หาตำแหน่งที่ x ของผู้เล่นจะถูกแทรก — จะพาไปอยู่ระหว่างศัตรูสองตัวที่ใกล้ที่สุดในแกน x ด้วย O(log n) จากนั้นเดินออกจากจุดนั้นทั้งสองทิศทาง ตรวจระยะห่างจริง (x, y) และหยุดขยายเมื่อระยะห่างในแกน x เพียงอย่างเดียวของตัวที่เหลือมากกว่าระยะที่ดีที่สุดที่เจอแล้ว (เพราะระยะจริงมีแต่จะมากกว่านั้น) วิธีนี้เปลี่ยนกรณีทั่วไปให้เหลือประมาณ O(log n) แทน O(n) โดยแลกกับการต้องคอยอัปเดตดัชนีที่เรียงตาม x ให้ทันเมื่อศัตรูขยับ (การอัปเดตแบบเกือบเรียงแล้วที่เหมาะกับ insertion sort เหมือนรายการความลึกด้านบน) สำหรับศัตรูที่กระจายอยู่ในพื้นที่ 2D เปิดโล่งแทนที่จะอยู่ตามแนวเส้นคร่าว ๆ spatial hash grid — แบ่งศัตรูตามช่องกริด แล้วตรวจแค่ช่องของผู้เล่นกับช่องข้างเคียง — จะขยายผลได้ดีกว่าการเรียงมิติเดียว

เจาะลึกเพิ่มเติม

• MIT 6.006 Introduction to Algorithms — เลกเชอร์เรื่องการค้นหาและการจัดเรียง
• Stanford CS161 — Design and Analysis of Algorithms — การวิเคราะห์ merge sort, quicksort และขีดจำกัดล่าง
• CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms — บทที่ ๒ (insertion sort และแนวคิด divide-and-conquer), บทที่ ๖ (heapsort), บทที่ ๗ (quicksort), บทที่ ๘ (ขีดจำกัดล่าง Ω(n log n) ของ comparison sort พร้อม counting/radix sort ที่เอาชนะมันได้)
• Sedgewick & Wayne, Algorithms (ฉบับที่ ๔), Princeton — อธิบายชัดเจนมาก เน้นโค้ดจริง ครอบคลุมทุกอัลกอริทึมในบทนี้ พร้อมเปรียบเทียบประสิทธิภาพเชิงประจักษ์อย่างเข้มงวด
• Knuth, The Art of Computer Programming, เล่ม ๓ — “Sorting and Searching” — งานเจาะลึกที่สุดในเรื่องนี้ เป็นที่มาของการวิเคราะห์ขีดจำกัดล่างของ comparison sort และตัวแปรการจัดเรียงนับสิบแบบอย่างละเอียดที่สุด
• Roughgarden, Algorithms Illuminated, เล่ม ๑ — อธิบายที่มาของขอบเขต O(n log n) ของ merge sort ผ่าน recursion tree อย่างเข้าถึงง่ายแต่เข้มงวด เหมาะคู่กับ Stanford CS161
• VisuAlgo — Sorting — เครื่องมือแสดงภาพการทำงานของอัลกอริทึมจัดเรียงแบบโต้ตอบ