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