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

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

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

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

ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด O ( n ) {\displaystyle O(n)}
ประเภท ขั้นตอนวิธีการเรียงลำดับ
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป O ( n 2 ) {\displaystyle O(n^{2})}
โครงสร้างข้อมูล รายการ
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด ใช้พื่นที่ O ( 1 ) {\displaystyle O(1)} เพิ่มเติม
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด O ( n 2 ) {\displaystyle O(n^{2})}

ใกล้เคียง

การเรียนรู้ของเครื่อง การเร่งปฏิกิริยา การเรืองแสงของบรรยากาศ การเรียนรู้เชิงลึก การเร็นเดอร์ การเรียน การเรียกยานพาหนะคืนของโตโยต้า พ.ศ. 2552−2553 การเรียงลำดับแบบฟอง การเรียกชื่อสารเคมีตามระบบไอยูแพ็ก การเร่งโดยอาศัยแอนติบอดี