Advanced Sorting

Quick Sort คืออะไร

Quick Sort คืออัลกอริทึมเรียงข้อมูลแบบ Divide and Conquer ที่ทำงานโดยเลือกค่าหนึ่งมาเป็นตัวอ้างอิง (pivot) แล้วจัดระเบียบให้ค่าที่น้อยกว่า pivot อยู่ฝั่งซ้าย และค่าที่มากกว่าหรือเท่ากับอยู่ฝั่งขวา — กระบวนการนี้เรียกว่า partition

หลัง partition เสร็จ pivot จะอยู่ในตำแหน่งสุดท้ายที่ถูกต้องของมันทันที — จากนั้นเรียกซ้ำ (recursive) กับฝั่งซ้ายที่เล็กกว่าและฝั่งขวาที่ใหญ่กว่าจนครบทั้งอาเรย์

• Average O(n log n) — เร็วมากในทางปฏิบัติ และมักเร็วกว่า Merge Sort เพราะ cache-friendly
• In-place — จัดเรียงภายในอาเรย์เดิม (ไม่ต้องสร้างอาเรย์ใหม่แบบ Merge Sort)
• Worst case O(n²) — เกิดเมื่อ pivot แบ่งข้อมูลไม่สมดุล เช่น เลือก pivot ตัวแรก/ท้ายกับข้อมูลที่เรียงแล้ว

แนวคิดหลัก: Pivot + Partition + Recursion

Quick Sort แยกเป็น 3 ส่วนที่ทำงานสอดประสานกัน: pivot (ค่าอ้างอิง), partition (จัดสมาชิกรอบ pivot), และ recursion (เรียกฟังก์ชันเดิมกับช่วงย่อยที่ยังไม่เรียง)

• เลือก pivot — เลือกค่าหนึ่งในอาเรย์เป็นตัวอ้างอิง (เช่น ตัวแรก ตัวท้าย ค่ากลาง หรือสุ่ม)
• ทำ partition — วนจัดสมาชิกทุกตัว: น้อยกว่า pivot → ซ้าย, มากกว่าหรือเท่ากับ → ขวา — pivot จะไปอยู่ในตำแหน่งที่ถูกต้องทันที
• เรียกซ้ำ — เรียก Quick Sort กับช่วงซ้าย [low..pivotIndex-1] และช่วงขวา [pivotIndex+1..high]

Pivot — ตัวแบ่งพรมแดน

Pivot คือค่าในอาเรย์ที่เราหยิบขึ้นมาเป็น "เส้นแบ่ง" — ค่าที่น้อยกว่า pivot จะถูกย้ายไปทางซ้าย ค่าที่มากกว่าหรือเท่ากับจะถูกย้ายไปทางขวา คุณภาพของ pivot เป็นตัวกำหนดประสิทธิภาพทั้งอัลกอริทึม

แผนภาพแสดงตำแหน่ง pivot — ตัวแรก ตัวท้าย หรือค่ากลาง

• เลือกตัวท้าย (last element) — เขียนง่ายสุด ใช้ในบทนี้เพื่อความเรียบง่าย แต่เสี่ยง worst case ถ้าข้อมูลเรียงแล้ว
• เลือกตัวแรก (first element) — คล้ายตัวท้าย แค่เปลี่ยนตำแหน่ง pivot — เสี่ยง worst case เช่นกันหากข้อมูลเรียงกลับด้าน
• เลือกสุ่ม (random pivot) — ลดโอกาส worst case เพราะไม่ขึ้นกับรูปแบบข้อมูล แต่เพิ่ม overhead สุ่มเล็กน้อย

ในทางปฏิบัติ library ส่วนใหญ่ใช้ median-of-three (เลือก 3 ค่า: ตัวแรก กลาง ท้าย แล้วเอาค่ามัธยฐาน) หรือ random pivot — เพราะลดความเสี่ยงจากข้อมูลที่มีรูปแบบทำให้เกิด worst case ได้ดี

Partition — จัดสมาชิกรอบ pivot

Partition คือหัวใจที่สำคัญที่สุดของ Quick Sort — เป็นขั้นตอนการจัดเรียงสมาชิกในอาเรย์ให้ค่าที่น้อยกว่า pivot อยู่ด้านซ้าย และค่าที่มากกว่าหรือเท่ากับ pivot อยู่ด้านขวา หลัง partition เสร็จ pivot จะถูกวางในตำแหน่งที่ถูกต้องของมัน

ในตัวอย่างของเราใช้ pivot เป็นตัวท้ายของช่วง (Lomuto partition scheme): 1. ตั้ง i = low - 1 (ตัวชี้ขอบเขตของ "ฝั่งน้อยกว่า pivot") 2. ใช้ j วิ่งจาก low ถึง high-1 — ถ้า arr[j] <= pivot ให้ขยายฝั่งซ้าย (i++) แล้วสลับ arr[i] กับ arr[j] 3. หลังวนจบ: สลับ arr[i+1] กับ arr[high] (ตัว pivot) — pivot จะอยู่ในตำแหน่ง i+1 ซึ่งถูกต้องแล้ว

ภาพการแบ่งข้อมูลรอบ pivot — ซ้ายน้อยกว่า ขวามากกว่า

ภาพ step-by-step การ partition — เปรียบเทียบและสลับทีละตำแหน่ง

Code Trace: Partition ทีละขั้น

ดูการทำงานของ partition แบบ step-by-step กับอาเรย์ [10, 7, 8, 9, 1, 5] ที่เลือก pivot = 5 (ตัวท้าย) — สังเกตการเปลี่ยนแปลงของ i, j, arr ทุกครั้งที่เข้าเงื่อนไข arr[j] <= pivot

ผลลัพธ์: อาเรย์กลายเป็น [1, 5, 8, 9, 10, 7] — 5 อยู่ index 1 พอดี โดยซ้ายมีแค่ 1 (น้อยกว่า 5) และขวามี 8,9,10,7 (มากกว่า 5) — จากนั้น Quick Sort จะเรียกซ้ำกับฝั่งซ้าย [0..0] (1 ตัว = เรียงแล้ว) และฝั่งขวา [2..5] (ต้อง partition ต่อ)

ตัวอย่างการทำงานทั้งอัลกอริทึม

ต่อจาก partition รอบแรกที่ pivot=5 ได้อาเรย์ [1, 5, 8, 9, 10, 7] — ฝั่งซ้าย [1] มีสมาชิกเดี่ยว = จบทันที (base case), ฝั่งขวา [8, 9, 10, 7] ต้อง partition ต่ออีกหลายรอบ

รอบที่ 2 (ฝั่งขวา): pivot = 7 หลัง partition → [7, 8, 10, 9] — pivot=7 อยู่ index 2 → ฝั่งซ้ายว่าง (จบ) → ฝั่งขวา [8,10,9] partition ต่อ รอบที่ 3: pivot = 9 → [8, 9, 10] — pivot=9 อยู่ index 5 → ฝั่งซ้าย [8] จบ → ฝั่งขวา [10] จบ ผลลัพธ์สุดท้าย: [1, 5, 7, 8, 9, 10]

ภาพการเรียกซ้ำฝั่งซ้ายและฝั่งขวา — partition ไปจนครบทุกช่วง

โค้ด Quick Sort

ฟังก์ชัน quickSort(arr, low, high):
  ถ้า low >= high:
    คืนค่า

  pivotIndex = partition(arr, low, high)

  quickSort(arr, low, pivotIndex - 1)
  quickSort(arr, pivotIndex + 1, high)

ฟังก์ชัน partition(arr, low, high):
  pivot = arr[high]  // เลือกตัวท้ายเป็น pivot
  i = low - 1       // ขอบเขตของโซน "น้อยกว่า pivot"

  ทำซ้ำ j จาก low ถึง high - 1:
    ถ้า arr[j] <= pivot:
      i = i + 1
      สลับ arr[i] กับ arr[j]

  สลับ arr[i + 1] กับ arr[high]  // วาง pivot ในตำแหน่งที่ถูกต้อง
  คืนค่า i + 1

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j += 1) {
    if (arr[j] <= pivot) {
      i += 1;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low >= high) {
    return arr;
  }

  const pivotIndex = partition(arr, low, high);

  quickSortInPlace(arr, low, pivotIndex - 1);
  quickSortInPlace(arr, pivotIndex + 1, high);

  return arr;
}

function quickSort(values) {
  const arr = [...values];
  return quickSortInPlace(arr);
}

console.log(quickSort([10, 7, 8, 9, 1, 5]));
// [1, 5, 7, 8, 9, 10]

โครงสร้าง 3 ฟังก์ชัน: `quickSort` (public API — shallow copy + ป้องกัน side effect), `quickSortInPlace` (recursive entry — base case + partition + recursive calls), `partition` (หัวใจ — จัดสมาชิกรอบ pivot แบบ in-place)

Time & Space Complexity

Space Complexity: Quick Sort แบบ in-place ใช้พื้นที่เสริมแค่ call stack ของ recursion — เฉลี่ย O(log n) (ต้นไม้สมดุล) แต่กรณีแย่สุดอาจลึกถึง O(n) (ต้นไม้ไม่สมดุลสุดขีด) — ดีกว่า Merge Sort ที่ต้องใช้ O(n) เสริมแน่ ๆ

การเลือก pivot และกลยุทธ์ลด Worst Case

ประสิทธิภาพของ Quick Sort ขึ้นกับการเลือก pivot แทบทั้งหมด — เลือกดี (แบ่งสมดุล) → เร็วระดับ O(n log n) — เลือกไม่ดีซ้ำ ๆ → ตกเป็น O(n²) — มาดูกลยุทธ์ที่ใช้ในทางปฏิบัติ

• ตัวท้าย / ตัวแรก — เขียนง่าย แต่เสี่ยง worst case ถ้าข้อมูลมีรูปแบบ (เรียงแล้ว / เรียงกลับด้าน)
• Random pivot — สุ่มเลือก pivot ก่อน partition โอกาส worst case ต่ำมาก โดยไม่ขึ้นกับรูปแบบข้อมูลเลย
• Median-of-three — เลือก arr[low], arr[mid], arr[high] แล้วเอาค่ามัธยฐาน — สมดุลและเชื่อถือได้ ใช้ใน library จริงหลายตัว

ข้อดี ข้อเสีย และเปรียบเทียบกับ Merge Sort

• โดยเฉลี่ยทำงานเร็วมาก — เร็วกว่า Merge Sort ในทางปฏิบัติเพราะ cache-friendly (ทำงานบนอาเรย์เดิม ไม่สร้างใหม่)
• In-place — ใช้หน่วยความจำเสริม O(log n) (call stack) ดีกว่า Merge Sort ที่ต้อง O(n)
• แนวคิด pivot + partition ใช้ได้ดีกับปัญหาอื่น เช่น Quickselect (หาค่าที่ k น้อยสุด) ใน O(n) เฉลี่ย

• มี worst case O(n²) — ถ้าเลือก pivot ไม่ดีซ้ำ ๆ เร็วกว่า Insertion Sort บนข้อมูลเล็กก็จริง แต่แย่กว่า Merge Sort มาก
• โค้ด partition (in-place) สำหรับมือใหม่อ่านยาก — ต้องเข้าใจ i, j, และการสลับค่าพร้อมกัน
• ไม่ใช่ stable sort แบบพื้นฐาน — การสลับ in-place ทำให้ลำดับของค่าที่เท่ากันเปลี่ยนแปลงได้

เลือก Quick Sort เมื่อต้องการ in-place, ข้อมูลอยู่ในอาเรย์, และยอมรับ worst case ได้ (หรือใช้ random/median-of-three pivot) — เลือก Merge Sort เมื่อต้องการ stable sort, คาดเดาเวลาได้แน่นอน, หรือเรียง linked list

ทบทวนความเข้าใจ

แบบฝึกหัดที่ 1: partitionByPivot — แยกข้อมูลรอบ pivot

เริ่มจากแกนของ Quick Sort — ฟังก์ชัน partitionByPivot ที่รับอาเรย์กับ pivot แล้วแยกค่าออกเป็นฝั่งน้อยกว่า (less) และฝั่งมากกว่าหรือเท่ากับ (greaterOrEqual)

แบบฝึกหัดที่ 2: quickSort — เรียงจากน้อยไปมาก

ใช้ partitionByPivot จาก Lab 01 มาสร้าง quickSort เต็มรูปแบบ — base case + เลือก pivot + partition + เรียกซ้ำกับซ้าย/ขวา

แบบฝึกหัดที่ 3: quickSortDescending — เรียงจากมากไปน้อย

ประยุกต์ Quick Sort เพื่อเรียงจากมากไปน้อย — แค่สลับฝั่งในขั้น partition และตอนประกอบผลลัพธ์