การเรียงลำดับแบบฟอง

การเรียงลำดับแบบฟอง (อังกฤษ: bubble sort) เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย มีประสิทธิภาพ O(n²)

ขั้นตอนวิธี

เปรียบเทียบข้อมูลในลิสต์ตัวปัจจุบันกับตัวถัดไป ในกรณีต้องการเรียงจาก น้อยไปมาก ถ้าตัวปัจจุบันมีค่ามากกว่าตัวถัดไปก็สลับที่กัน; ในกรณีต้องการเรียงจาก มากไปน้อย ถ้าตัวปัจจุบันมีค่าน้อยกว่าตัวถัดไป ก็สลับที่กัน และก็เปลี่ยนตำแหน่งปัจจุบันเป็นตำแหน่งถัดไปเรื่อย ๆ จนกว่าจะครบทุกตัว แล้วก็เริ่มใหม่ กระทำเช่นนี้ไปเรื่อย ๆ จนกว่าชุดข้อมูลนั้นจะเรียงเรียบร้อย

ตัวอย่าง

การเรียงลำดับเลข 5 1 2 8 ในลิสต์ ด้วยขั้นตอนวิธีแบบฟอง
ครั้งที่ 1
( 5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ), เปรียบเทียบตัวปัจจุบันกับตัวถัดไป สลับเนื่องจาก 5 > 1
( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ), สลับเนื่องจาก 5 > 4
( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ), สลับเนื่องจาก 5 > 2
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ), ไม่สลับเนื่องจาก 5 ไม่มากกว่า 8
ครั้งที่ 2
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 )
( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 ), สลับเนื่องจาก 4 > 2
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
ถึงแม้ว่าข้อมูลในลิสต์จะเรียงหมดแล้ว แต่ว่าก็ต้องตรวจสอบอีกครั้งหนึ่ง
ครั้งที่ 3
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
เรียงเสร็จเรียบร้อย