BUBBLE SORT

BUBBLE SORT

Sort เป็นแบบหนึ่งของ exchange sort หลักการมีอยู่ว่าว่าเราจะเปรียบเทียบค่า 2 ค่าที่ติดกัน ถ้าไม่ได้อยู่ในลำดับที่เรากำหนด เช่น จากน้อยไปมาก ก็ให้แลกเปลี่ยนตำแหน่งของค่าทั้ง 2 ค่านั้น แล้วเอาค่าน้อย (หรือค่ามาก ถ้าเป็นการเรียงจากค่ามากไปหาค่าน้อย) เปรียบเทียบกับค่าถัดไปอีกเป็นเช่นนี้ตลอดไปจนกว่าอยู่ในลำดับที่ถูกต้อง สมมติว่าเร Bubbleามีลิสต์ (5,1,2,8,9) เราจะเรียงโดยเทคนิคนี้ได้ดังรูปที่ 1 (โดยต้องการเรียงจากมากไปน้อยตามแนวบนลงล่าง

[Only admins are allowed to see this image]


รูปการเรียงแบบ bubble sort

ขั้นแรกให้นำเอา 5 เปรียบเทียบกับ 1 ปรากฏว่า 5 และ1 เรียงลำดับตามที่เราต้องการอยู่แล้ว จากนั้นให้นำเอา 1 เปรียบเทียบกับตัวถัดไปคือ 2 เนื่องจาก 2 มากกว่า 1 และ 2 อยู่ในตำแหน่งที่ผิดลำดับ จึงให้แลกที่กับ 1 หลังจากที่ 2 ไปอยู่ในตำแหน่งท่อยู่เดิมของ 1 (นั่นคือตำแหน่งที่ 2 )แล้วก็ให้ 2 เปรียบเทียบกับค่าในตำแหน่งที่ 1 คือ 5 ปรากฏอยู่ในลำดับที่ถูกต้อง ก็ไม่ต้องแลกที่กัน ต่อมานำ 1 ไปเปรียบเทียบกับ 8 แล้วทำในลักษณะเดิม ค่า 8 จะค่อย ๆ ลอยขึ้นไปอยู่ในตำแหน่งที่ถูกต้อง ในที่สุดก็นำ 1 ไปเปรียบเทียบกับ 9 เลข 9 จะค่อย ๆลอยขึ้นไปยังตำแหน่งที่ถูกต้อง )

สิ่งที่ต้องทำในการเรียงค่าคือ เปรียบเทียบ และแลกตำแหน่ง เราจะพิจารณากรณีปลายสุด 2 กรณี คือ

1)ถ้าลิสต์นั้นเป็นลิสต์ที่เรียงเรียบร้อยแล้วจากมากไปน้อย และเราบังเอิญต้องการเรียงจากมากไปน้อยโดยใช้ bubble sort เราจะสามารถทำได้โดยไม่ต้องมีการแลกตำแหน่งเลยและต้องทำการเปรียบเทียบ เพียง n - 1 ครั้งเท่านั้น (ถ้ามีข้อมูล n ตัว)

(2)ถ้าลิสต์นั้นเป็นลิสต์ที่เรียงเรียบร้อยแล้วจากน้อยไปมากและเราต้องการเรียงมันจากมากไปน้อย เราต้องทำการแลกเปลี่ยนและเปรียบเทียบเป็นจำนวน 1 + 2 + 3 + … +(n - 1) ครั้งหรือเท่ากับ n(n - 1) / 2 ครั้งนั่นเอง

จะเห็นได้ว่า bubble sort จะดีหรือเลวก็ขึ้นอยู่กับว่าลิสต์นั้นเกือบเรียง ในลำดับที่เราต้องการจะเรียงมันหรือไม่ ถ้าค่าในลิสต์นั้นอยู่ในแบบ random ก็จะต้องมีการแลกเปลี่ยนประมาณ n(n - 1)/4 ครั้ง การเรียงข้อมูลแบบนี้จึงจัดเป็นพวก O(n2) ซิงเกิลตัน อาร์.ซี. (Singleton R.C. - Alogrithm 347 - CACM)พบว่าวิธีเรียงแบบ bubble จะดีที่สุดถ้าลิสต์นั้นมีค่าเท่ากับหรือน้อยกว่า 11 ตัว สรุปได้ว่าการเรียงข้อมูลแบบนี้ไม่เหมาะกับลิสต์ขนาดยาว ๆ อย่างไรก็ดีวิธีเรียงแบบนี้สามารถจำได้ง่ายและโปรแกรมได้ง่ายขึ้น


*เครดิต [Only admins are allowed to see this link]



ขั้นตอนวิธี Bubble sort
Bubble sort เป็นการเรียงโดยสลับค่าที่อยู่ติดกันให้อยู่ในลำดับที่เรียงกัน ขั้นตอนวิธีดังนี้ BUBBLE-SORT(A) เมื่อ A เป็น array
ข้อมูลเข้า A[1..n]
ข้อมูลออก การจัดเรียงของข้อมูลจำนวน n ตัวใน A โดยที่ A[1] A[2] A[3] . . . A[n]
BUBBLE-SORT(A)
1. for i =1 to n-1
2. for j = 1 to n - i
3. if A[j] > A[j+1] then
4. (A[j], A[j+1]) = (A[j+1], A[j])
5. endif
6. endfor
7. endfor


*เครดิต [Only admins are allowed to see this link]