การค้นหาและการเรียงลำดับบทที่ 21Quick Sort

Quick Sort แบบละเอียด: เข้าใจ Pivot, Partition และ Recursion ให้ชัด

บทนี้จะพาเรียน Quick Sort ตั้งแต่แนวคิดพื้นฐานจนถึงการลงมือเขียนโค้ดจริง โดยเน้นให้เห็นภาพการแบ่งข้อมูลรอบ pivot และการเรียกซ้ำทีละฝั่งแบบเข้าใจง่าย

1. Quick Sort คืออะไร

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

หลังจากแบ่งแล้ว จะเรียกซ้ำแบบเดียวกันกับฝั่งซ้ายและฝั่งขวา จนทั้งอาเรย์เรียงครบ

2. แนวคิดหลักของ Quick Sort

แกนหลักมี 3 ขั้น: เลือก pivot, ทำ partition, แล้วเรียกซ้ำ (recursive sorting) กับช่วงย่อยที่ยังไม่เรียง

จุดสำคัญคือหลัง partition เสร็จ pivot จะอยู่ตำแหน่งที่ถูกต้องของมันในอาเรย์ทันที

3. Pivot คืออะไร

Pivot คือค่าที่เราเลือกมาเป็น “เส้นแบ่ง” เพื่อจัดสมาชิกอื่นว่าอยู่ฝั่งซ้ายหรือขวา โดยเลือกได้หลายแบบ เช่น ตัวแรก ตัวท้าย ค่ากลาง หรือ median-of-three

แผนภาพแสดงตำแหน่ง pivot ที่เลือกได้ เช่น กลางชุดข้อมูลหรือท้ายชุดข้อมูล

4. Partition คืออะไร

Partition คือขั้นตอนการจัดข้อมูลรอบ pivot: ค่าที่น้อยกว่า pivot ไปฝั่งซ้าย, ค่าที่มากกว่าหรือเท่ากับไปฝั่งขวา

หลังทำ partition เสร็จ pivot จะถูกวางในตำแหน่งใหม่ที่ถูกต้อง และเราไม่ต้องขยับ pivot ตัวนั้นอีก

ภาพแสดงการแบ่งข้อมูลเป็นฝั่งน้อยกว่า pivot และฝั่งมากกว่าหรือเท่ากับ pivot

5. อธิบายภาพรวมการทำงาน

เริ่มจากอาเรย์เต็ม เลือก pivot แล้ว partition หนึ่งรอบ จากนั้นจะแตกเป็นช่วงซ้ายและช่วงขวาที่เล็กลง

Quick Sort จะทำซ้ำตรรกะเดิมกับทั้งสองช่วงจนกระทั่งช่วงนั้นมีสมาชิก 0 หรือ 1 ตัว ซึ่งถือว่าเรียงแล้ว

6. ตัวอย่าง array เช่น [10, 7, 8, 9, 1, 5]

เราจะใช้อาเรย์ตัวอย่าง[10, 7, 8, 9, 1, 5]และเลือก pivot เป็นตัวท้ายของช่วงในแต่ละรอบ

7. เลือก pivot แล้วอธิบายการแบ่งค่าที่น้อยกว่าและมากกว่า pivot

รอบแรก pivot = 5 (ตัวท้าย) เมื่อ partition ค่า 1 จะถูกย้ายมาอยู่ซ้าย pivot และค่าที่เหลือที่มากกว่า จะอยู่ทางขวา สถานะหลังจบรอบแรกคือ [1, 5, 8, 9, 10, 7]

ภาพแบบ step-by-step แสดงการ partition ของ Quick Sort พร้อมการเปรียบเทียบและสลับค่า

8. อธิบายการเรียกซ้ำกับฝั่งซ้ายและฝั่งขวา

หลัง pivot = 5 อยู่ถูกตำแหน่งแล้ว จะเหลือฝั่งซ้าย [1] และฝั่งขวา [8, 9, 10, 7] ฝั่งซ้ายมีตัวเดียวจบทันที ส่วนฝั่งขวายังต้อง partition ต่อ

ทำซ้ำแบบเดียวกันกับฝั่งขวาไปเรื่อย ๆ จนทุกช่วงเล็กพอ (0 หรือ 1 ตัว) สุดท้ายจะได้ [1, 5, 7, 8, 9, 10]

ภาพแสดงการ recursive sort ของฝั่งซ้ายและฝั่งขวาหลังการ partition

9. Pseudocode

Pseudocode: Quick Sortbash

โครงคิดหลักของ quickSort และ partition

ฟังก์ชัน 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

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

  สลับ arr[i + 1] กับ arr[high]
  คืนค่า i + 1

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: Quick SortJS

ใช้ partition แบบเลือก pivot เป็นสมาชิกตัวท้าย

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]

ฟังก์ชัน `partition` ทำหน้าที่จัดค่ารอบ pivot และคืน pivotIndex จากนั้น `quickSortInPlace` เรียกซ้ำกับช่วงซ้าย/ขวาโดยใช้ pivotIndex เป็นจุดแบ่ง

11. Best / Average / Worst Time Complexity

Best: O(n log n)

เกิดเมื่อ pivot แบ่งข้อมูลได้ใกล้เคียงครึ่งซ้าย/ขวาในหลายรอบ

Average: O(n log n)

โดยทั่วไปหาก pivot ไม่แย่เกินไป การแบ่งจะค่อนข้างสมดุล

Worst: O(n²)

เกิดเมื่อ pivot แบ่งได้แย่มาก เช่น ได้ช่วงหนึ่งยาวเกือบทั้งหมดทุกครั้ง

12. Space Complexity

ถ้าเป็น in-place quick sort จะใช้พื้นที่เสริมหลัก ๆ จาก call stack ของ recursion: เฉลี่ยประมาณ O(log n) และกรณีแย่สุดอาจสูงถึง O(n)

13. ข้อดี

โดยเฉลี่ยทำงานเร็วมาก และมักเร็วในงานจริง

แบบ in-place ใช้หน่วยความจำเสริมน้อยเมื่อเทียบกับ Merge Sort

แนวคิดแบ่งแล้วจัดรอบ pivot ช่วยให้เข้าใจการออกแบบอัลกอริทึมเชิง recursion

14. ข้อเสีย

ประสิทธิภาพแย่สุดเป็น O(n²) หากเลือก pivot ไม่ดีต่อเนื่อง

โค้ด partition สำหรับผู้เริ่มต้นอาจอ่านยากช่วงแรก

อัลกอริทึมแบบพื้นฐานไม่ใช่ stable sort

15. กรณีที่อาจเกิด worst case

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

16. วิธีเลือก pivot แบบคร่าว ๆ

วิธีง่าย

เลือกตัวท้ายหรือตัวแรก เขียนง่าย แต่เสี่ยง worst case ถ้าข้อมูลมีรูปแบบบางแบบ

วิธีที่สมดุลขึ้น

ใช้ random pivot หรือ median-of-three (ตัวแรก-กลาง-ท้าย) ช่วยลดโอกาสแบ่งไม่สมดุลซ้ำ ๆ

17. เปรียบเทียบกับ Merge Sort

Quick Sort

เฉลี่ยเร็วมากและใช้หน่วยความจำเสริมน้อย (in-place) แต่มี worst case O(n²)

Merge Sort

เวลา O(n log n) คงเส้นคงวากว่า แต่ต้องใช้อาเรย์เสริม O(n)

18. สรุปท้ายบท

Quick Sort คือการเลือก pivot แล้ว partition ให้ซ้ายเล็กกว่า ขวาใหญ่กว่า จากนั้นเรียกซ้ำกับช่วงย่อยจนเรียงครบทั้งอาเรย์

ถ้าเข้าใจ pivot + partition ชัดเจน คุณจะอ่านและเขียน Quick Sort ได้มั่นใจมากขึ้น และต่อยอดไปอัลกอริทึมเชิง recursion อื่นได้ง่าย

19. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย (use playground)

ข้อ 1: เขียน `partitionByPivot(values, pivot)` ให้คืน less และ greaterOrEqual

แนวเฉลยย่อ: วนทีละค่า ถ้าน้อยกว่า pivot ใส่ less ไม่งั้นใส่ greaterOrEqual

ข้อ 2: เขียน `quickSort(values)` ให้เรียงจากน้อยไปมาก

แนวเฉลยย่อ: base case ความยาว <= 1, เลือก pivot, partition, แล้วประกอบผลเป็น quickSort(left) + pivot + quickSort(right)

ข้อ 3: เขียน `quickSortDescending(values)` ให้เรียงจากมากไปน้อย

แนวเฉลยย่อ: ใช้โครงเดิม แต่สลับฝั่งเปรียบเทียบ และประกอบผลให้ฝั่งมากกว่าอยู่ก่อน

ไปฝึกลงมือจริงใน Quick Sort Lab ได้ทันที มี runtime checks ให้ตรวจผลลัพธ์แบบอัตโนมัติ

ไปทำ Quick Sort Lab

การค้นหาและการเรียงลำดับบทที่ 21Quick Sort

Quick Sort แบบละเอียด: เข้าใจ Pivot, Partition และ Recursion ให้ชัด

1. Quick Sort คืออะไร

2. แนวคิดหลักของ Quick Sort

3. Pivot คืออะไร

4. Partition คืออะไร

5. อธิบายภาพรวมการทำงาน

6. ตัวอย่าง array เช่น [10, 7, 8, 9, 1, 5]

7. เลือก pivot แล้วอธิบายการแบ่งค่าที่น้อยกว่าและมากกว่า pivot

8. อธิบายการเรียกซ้ำกับฝั่งซ้ายและฝั่งขวา

9. Pseudocode

Pseudocode: Quick Sortbash

โครงคิดหลักของ quickSort และ partition

ฟังก์ชัน 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

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

  สลับ arr[i + 1] กับ arr[high]
  คืนค่า i + 1

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: Quick SortJS

ใช้ partition แบบเลือก pivot เป็นสมาชิกตัวท้าย

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]

11. Best / Average / Worst Time Complexity

Best: O(n log n)

เกิดเมื่อ pivot แบ่งข้อมูลได้ใกล้เคียงครึ่งซ้าย/ขวาในหลายรอบ

Average: O(n log n)

โดยทั่วไปหาก pivot ไม่แย่เกินไป การแบ่งจะค่อนข้างสมดุล

Worst: O(n²)

เกิดเมื่อ pivot แบ่งได้แย่มาก เช่น ได้ช่วงหนึ่งยาวเกือบทั้งหมดทุกครั้ง

12. Space Complexity

13. ข้อดี

โดยเฉลี่ยทำงานเร็วมาก และมักเร็วในงานจริง

แบบ in-place ใช้หน่วยความจำเสริมน้อยเมื่อเทียบกับ Merge Sort

แนวคิดแบ่งแล้วจัดรอบ pivot ช่วยให้เข้าใจการออกแบบอัลกอริทึมเชิง recursion

14. ข้อเสีย

ประสิทธิภาพแย่สุดเป็น O(n²) หากเลือก pivot ไม่ดีต่อเนื่อง

โค้ด partition สำหรับผู้เริ่มต้นอาจอ่านยากช่วงแรก

อัลกอริทึมแบบพื้นฐานไม่ใช่ stable sort

15. กรณีที่อาจเกิด worst case

16. วิธีเลือก pivot แบบคร่าว ๆ

วิธีง่าย

วิธีที่สมดุลขึ้น

ใช้ random pivot หรือ median-of-three (ตัวแรก-กลาง-ท้าย) ช่วยลดโอกาสแบ่งไม่สมดุลซ้ำ ๆ

17. เปรียบเทียบกับ Merge Sort

Quick Sort

เฉลี่ยเร็วมากและใช้หน่วยความจำเสริมน้อย (in-place) แต่มี worst case O(n²)

Merge Sort

เวลา O(n log n) คงเส้นคงวากว่า แต่ต้องใช้อาเรย์เสริม O(n)

18. สรุปท้ายบท

19. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย (use playground)

ข้อ 1: เขียน `partitionByPivot(values, pivot)` ให้คืน less และ greaterOrEqual

แนวเฉลยย่อ: วนทีละค่า ถ้าน้อยกว่า pivot ใส่ less ไม่งั้นใส่ greaterOrEqual

ข้อ 2: เขียน `quickSort(values)` ให้เรียงจากน้อยไปมาก

แนวเฉลยย่อ: base case ความยาว <= 1, เลือก pivot, partition, แล้วประกอบผลเป็น quickSort(left) + pivot + quickSort(right)

ข้อ 3: เขียน `quickSortDescending(values)` ให้เรียงจากมากไปน้อย

ไปฝึกลงมือจริงใน Quick Sort Lab ได้ทันที มี runtime checks ให้ตรวจผลลัพธ์แบบอัตโนมัติ

ไปทำ Quick Sort Lab

Data Structures & Algorithms

1. Quick Sort คืออะไร

2. แนวคิดหลักของ Quick Sort

3. Pivot คืออะไร

4. Partition คืออะไร

5. อธิบายภาพรวมการทำงาน

6. ตัวอย่าง array เช่น [10, 7, 8, 9, 1, 5]

7. เลือก pivot แล้วอธิบายการแบ่งค่าที่น้อยกว่าและมากกว่า pivot

8. อธิบายการเรียกซ้ำกับฝั่งซ้ายและฝั่งขวา

9. Pseudocode

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

11. Best / Average / Worst Time Complexity

12. Space Complexity

13. ข้อดี

14. ข้อเสีย

15. กรณีที่อาจเกิด worst case

16. วิธีเลือก pivot แบบคร่าว ๆ

17. เปรียบเทียบกับ Merge Sort

18. สรุปท้ายบท

19. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย (use playground)

Loading

Data Structures & Algorithms

1. Quick Sort คืออะไร

2. แนวคิดหลักของ Quick Sort

3. Pivot คืออะไร

4. Partition คืออะไร

5. อธิบายภาพรวมการทำงาน

6. ตัวอย่าง array เช่น [10, 7, 8, 9, 1, 5]

7. เลือก pivot แล้วอธิบายการแบ่งค่าที่น้อยกว่าและมากกว่า pivot

8. อธิบายการเรียกซ้ำกับฝั่งซ้ายและฝั่งขวา

9. Pseudocode

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

11. Best / Average / Worst Time Complexity

12. Space Complexity

13. ข้อดี

14. ข้อเสีย

15. กรณีที่อาจเกิด worst case

16. วิธีเลือก pivot แบบคร่าว ๆ

17. เปรียบเทียบกับ Merge Sort

18. สรุปท้ายบท

19. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย (use playground)