ประสิทธิภาพ

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

การปรับปรุงประสิทธิภาพของการเรียงลำดับแบบฟองนั้นวิธีการหนึ่งก็คือการทำให้ค่าน้อยที่อยู่หลังๆ นั้นลงมาด้านหน้าได้เร็วขึ้น นั่นคือหลักการของ Cocktail Sort ซึ่งมีขั้นตอนวิธีคล้ายการเรียงลำดับแบบฟองมากเพียงแต่ทำงานทั้งขาไปและขากลับ ขาไปนั้นทำงานเหมือนการเรียงลำดับแบบฟองทุกประการ ส่วนขากลับก็เพียงกลับด้านของการเรียงลำดับแบบฟองนั่นเอง แต่การปรับปรุงดังนี้ก็ไม่ได้ทำให้ประสิทธิภาพในกรณีแย่ที่สุดดีกว่า O(n2) แต่อย่างใด

ตัวอย่างทีละขั้นตอน

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