การเรียงลำดับของฟองคืออะไร? - คำจำกัดความจาก techopedia

นิยาม - Bubble Sort หมายถึงอะไร

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

การเรียงลำดับฟองนั้นเรียกว่าการเรียงลำดับการจมหรือการเปรียบเทียบการเรียงลำดับ

Techopedia อธิบาย Bubble Sort

Bubble sort มีกรณีที่เลวร้ายที่สุดและมีความซับซ้อนโดยเฉลี่ยของ O (n2) โดยที่ n คือจำนวนรายการที่เรียงลำดับ ซึ่งแตกต่างจากอัลกอริทึมการเรียงลำดับอื่น ๆ การจัดเรียงฟองตรวจพบว่ารายการเรียงลำดับถูกสร้างขึ้นอย่างมีประสิทธิภาพในอัลกอริทึม ประสิทธิภาพของการเรียงลำดับฟองผ่านรายการที่เรียงลำดับแล้วคือ O (n)

ตำแหน่งขององค์ประกอบในการเรียงลำดับฟองมีบทบาทสำคัญในการกำหนดประสิทธิภาพ องค์ประกอบขนาดใหญ่ที่จุดเริ่มต้นไม่ก่อให้เกิดปัญหาตามที่สลับกันได้อย่างง่ายดาย องค์ประกอบขนาดเล็กไปยังจุดสิ้นสุดย้ายไปที่จุดเริ่มต้นช้า เช่นนี้องค์ประกอบเหล่านี้เรียกว่ากระต่ายและเต่า

อัลกอริทึมการจัดเรียงฟองสามารถปรับให้เหมาะสมโดยการวางองค์ประกอบขนาดใหญ่ในตำแหน่งสุดท้าย หลังจากผ่านทุกครั้งองค์ประกอบทั้งหมดหลังจากการสลับครั้งสุดท้ายจะถูกจัดเรียงและไม่จำเป็นต้องตรวจสอบอีกครั้งจึงข้ามการติดตามตัวแปรที่สลับเปลี่ยน