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