Quick Sort (median-of-three)
Quick sort เป็นวิธีการเรียงลำดับที่อาศัยการทำงานแบบ divide and conquer
(เหมือน merge sort แต่มีหลักการทำงานต่างกัน)
โดยแบ่งอาเรย์ออกเป็นสองชุดด้วยวิธีแบ่งส่วน (partiion) ให้ชุดซ้ายมีข้อมูลไม่มากกว่าชุดขวา
เมื่อนำชุดซ้ายไปเรียงลำดับ แล้วก็นำชุดขวาไปเรียงลำดับ จะได้ข้อมูลทั้งหมดเรียงทันทีแล้ว (เพราะชุดซ้ายมีข้อมูลไม่มากกว่าชุดขวา)
การแบ่งส่วนข้อมูลทำได้หลายวิธี วิธีที่ใช้ในการทดลองนี้คือ
การใช้มัธยฐานจากข้อมูลสามตัว (median of three) เป็นตัว pivot ในการแบ่งส่วน
(วิธีนี้ทำให้ข้อมูลที่เรียงลำดับแล้ว กับที่เรียงกลับลำดับ ไม่ใช่กรณีช้าสุด กลับเป็นสองกรณีที่ทำงานได้เร็วด้วยซ้ำไป)
ลองดูอีกวิธีคือ ใช้ตัวซ้ายสุดของกลุ่มเป็น pivot (วิธีนี้ไม่ค่อยดี แต่ลองเปรียบเทียบดู)
การทดลองข้างล่างนี้ป้อนข้อมูลเริ่มต้นให้กับ quick sort สามแบบ คือ
ข้อมูลเรียงเรียบร้อยแล้ว
ข้อมูลเรียงกลับลำดับ
และ
ข้อมูลสุ่ม
(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)
สมชาย ประสิทธิ์จูตระกูล