Insertion Sort
Insertion sort เป็นวิธีการเรียงลำดับที่ใช้กันมากกับปริมาณข้อมูลน้อย ๆ (หลักสิบตัว) เขียนโปรแกรมง่าย
มีคุณสมบัติพิเศษคือ "ยิ่งเรียงยิ่งเร็ว" อาศัยการพิจารณาข้อมูลไล่ตั้งแต่ตัวที่สองไปยังตัวท้าย
ขณะที่พิจารณาข้อมูลตัวที่ k ข้อมูลทางซ้ายทั้งหมด (ตัวที่ 1 ถึง k-1) เรียงเรียบร้อย ดังนั้นจึงต้องหาที่
"แทรก" ให้กับตัวที่ k เพื่อให้ในรอบถัดไป ตัวที่ 1 ถึง k เรียงเรียบร้อย ถ้าข้อมูลเรียงหรือค่อนข้างเรียงอยู่แล้ว
การหาที่แทรกจะกระทำได้รวดเร็ว ห่างจากตำแหน่งที่ k ไม่ค่อยมาก แต่ถ้าข้อมูลเรียงกลับลำดับ ก็จะช้ามาก ๆ
การทดลองข้างล่างนี้ป้อนข้อมูลเริ่มต้นให้กับ insertion sort สามแบบ คือ
ข้อมูลเรียงเรียบร้อยแล้ว
ข้อมูลเรียงกลับลำดับ
และ
ข้อมูลสุ่ม
พบว่า ทำงานได้เร็วมากเมื่อข้อมูลเรียงอยู่แล้ว ส่วนสองกรณีหลังมีภาระการทำงานมากกว่ามาก โดยกรณีข้อมูลเรียงกลับลำดับจะมีภาระมากกว่า
ถึงแม้ผลของลักษณะของข้อมูลขาเข้าต่อเวลาการทำงานของ insertion sort จะคล้ายกับของ
bubble sort
แต่ถ้าดูเทียบกันแล้ว insertion sort มีภาระการทำงานน้อยกว่า (ทำไมจึงเป็นเช่นนั้น ?)
(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)
สมชาย ประสิทธิ์จูตระกูล