การเรียงข้อมูลแบบ Bubble sort

การจัดเรียงข้อมูลแบบฟองอากาศ หรือ bubble sort

การเรียงข้อมูลแบบ Bubble Sort จะทำโดยการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันทีละคู่ไปเรื่อยๆ ในกรณีเรียง ลำดับข้อมูลจากน้อยไปมาก ถ้าค่าแรกมีค่ามากกว่าค่าสองก็จะทำการสลับที่กัน โดยวิธีการนี้ จะทำให้ ข้อมูลที่มีค่าน้อยกว่าลอยสูงขึ้นเรื่อยเหมือนฟองสบู่(bubble) ที่ลอยขึ้นที่สูง และข้อมูลที่น้อยที่สุดก็จะ อยู่ในต่ำแหน่งบนสุดของชุดข้อมูลจึงเรียกการเรียงลำดับวิธีนี้ว่า BUBBLE  SORT

สมมติว่าต้องการเรียงข้อมูลจากน้อยไปมาก จะทำการเปรียบเทียบข้อมูลทีละ 2 ตัว ถ้าข้อมูลตัวแรกมากกว่าจะทำการสลับค่ากับข้อมูลตัวที่ 2 และเปรียบเทียบข้อมูลอีก 2 ตัวถัดไปจนสุดอาร์เรย์ จากนั้นทำซ้ำแบบเดิมอีกตามจำนวนข้อมูลในอาร์เรย์-1 เช่น ถ้าข้อมูลในอาร์เรย์มีจำนวน 5 ช่อง ก็ต้องทำซ้ำเป็นจำนวน 4 ครั้ง เป็นต้น

ยกตัวอย่างชุดข้อมูล 5 1 4 2 8 

bubble sort ครั้งที่ 1  

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), เปรียบเทียบข้อมูล ตัวที่ 1 และ 2 : 5>1 สลับค่า 

( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), เปรียบเทียบข้อมูล ตัวที่ 2 และ 3 : 5>4 สลับค่า  

( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), เปรียบเทียบข้อมูล ตัวที่ 3 และ 4 : 5>2 สลับค่า 

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ),  เปรียบเทียบข้อมูล ตัวที่ 4 และ 5 : 5>8 ไม่ต้องสลับ

 หลังจากทำการเปรียบเทียบข้อมูลที่ละคู่ไปจนถึงลำดับสุดท้ายแล้ว ถ้าชุดข้อมูล ยังไม่เรียงจากน้อยไปหามาก ให้ทำการ bubble sort  อีกรอบ

bubble sort ครั้งที่ 2   

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )  เปรียบเทียบข้อมูล ตัวที่ 1 และ 2 : 1>4 ไม่สลับค่า

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ),  เปรียบเทียบข้อมูล ตัวที่ 2 และ 3 : 4>2 สลับค่า 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )  เปรียบเทียบข้อมูล ตัวที่ 3 และ 4 : 4>5 สลับค่า 

( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )   เปรียบเทียบข้อมูล ตัวที่ 4 และ 5 : 5>8 ไม่ต้องสลับ

ตอนนี้อาร์เรย์ได้รับการจัดเรียงแล้ว แต่อัลกอริธึมของเราไม่ทราบว่าเสร็จสิ้นหรือไม่ อัลกอริธึมต้องการหนึ่งรอบทั้งหมดโดยไม่มีการสลับเพื่อให้รู้ว่ามีการจัดเรียง

bubble sort ครั้งที่ 3  

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )