![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Bubblesort-edited-color.svg/langth-640px-Bubblesort-edited-color.svg.png&w=640&q=50)
การเรียงลำดับแบบฟอง
From Wikipedia, the free encyclopedia
ในสาขาวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบฟอง (อังกฤษ: bubble sort) เป็นขั้นตอนวิธีการเรียงลำดับที่เรียบง่ายมาก ดำเนินการบนโครงสร้างข้อมูลประเภทรายการ ทำงานโดยเปรียบเทียบสมาชิกที่อยู่ติดกัน เมื่อพบตำแหน่งที่ผิด (นั่นคือตัวหน้ามากกว่าตัวหลังในกรณีการเรียงจากน้อยไปมาก) ก็จะทำการสลับข้อมูลกัน และจะดำเนินการซ้ำแบบนี้ไปเรื่อยๆจนกว่าจะไม่มีตำแหน่งที่ผิดอีกซึ่งบ่งบอกว่ารายการนั้นเรียงแล้ว ชื่อของขั้นตอนวิธีนี้มีมาจากสมาชิกที่น้อยที่สุดจะค่อยๆถูกสลับขึ้นมาจนอยู่หน้าสุดของรายการ เปรียบได้กับฟองที่ค่อยๆผุดขึ้นมาถึงผิวน้ำ เนื่องจากขั้นตอนวิธีนี้ใช้เพียงการเปรียบเทียบจึงเป็นการเรียงแบบเปรียบเทียบ นอกจากนี้ยังเป็นการเรียงแบบเสถียรอีกด้วย ถึงแม้ว่าการเรียงลำดับแบบฟองจะเป็นขั้นตอนวิธีที่เรียบง่ายมาก แต่ไม่เหมาะในการเรียงข้อมูลจำนวนมากซึ่งมีวิธีการเรียงข้อมูลที่มีประสิทธิภาพมากกว่า
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
![]() ภาพจำลองการทำงานของการเรียงลำดับแบบฟอง | |
ประเภท | ขั้นตอนวิธีการเรียงลำดับ |
---|---|
โครงสร้างข้อมูล | รายการ |
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | ใช้พื่นที่ |
|