ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบฟอง"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล ย้อนการแก้ไขที่อาจเป็นการทดลอง หรือก่อกวนด้วยบอต ไม่ควรย้อน? แจ้งที่นี่ |
|||
บรรทัด 17:
[[ไฟล์:Bubble-sort-example-300px.gif|300px|thumb|right|ภาพตัวอย่างแสดงการทำงานของการเรียงลำดับแบบฟองเพื่อเรียงลำดับจากน้อยไปมาก เร่มต้นทำงานจากทางซ้ายและเปรียบเทียบทีละคู่และสลับกันถ้าหากพบว่าตัวทางด้านซ้ายมีค่ามากกว่าตัวทางด้านขวา]]
=== ประสิทธิภาพ ===
ประสิทธิภาพของการเรียงลำดับแบบฟองขึ้นอยู่กับตำแหน่งของข้อมูลต่างๆ ที่อยู่ในรายการ หากมีค่ามากอยู่ตัวแรกๆ การเรียงลำดับแบบฟองจะมีประสิทธิภาพดี เพราะว่าการทำงานเพียงรอบเดียวก็สามารถทำให้ค่ามากไปอยู่ในตำแหน่งที่ใกล้เคียงกับตำแหน่งจริงได้ เช่นมีค่ามากที่สุดอยู่ในตำแหน่งแรก การทำงานรอบเดียวก็เพียงพอที่จะลากค่านั้นไปอยู่ตำแหน่งสุดท้ายได้ แต่กลับกันหากมีค่าน้อยอยู่หลังๆ การทำงานหนึ่งรอบจะสามารถเลื่อนค่านั้นมาด้านหน้าได้เพียงเล็กน้อย เช่นหากค่านั้นเป็นค่าน้อยที่สุดการทำงานหนึ่งรอบจะเลื่อนค่านั้นมาด้านหน้าได้เพียงหนึ่งตำแหน่งเท่านั้น
การปรับปรุงประสิทธิภาพของการเรียงลำดับแบบฟองนั้นวิธีการหนึ่งก็คือการทำให้ค่าน้อยที่อยู่หลังๆ นั้นลงมาด้านหน้าได้เร็วขึ้น นั่นคือหลักการของ [[Cocktail Sort]] ซึ่งมีขั้นตอนวิธีคล้ายการเรียงลำดับแบบฟองมากเพียงแต่ทำงานทั้งขาไปและขากลับ ขาไปนั้นทำงานเหมือนการเรียงลำดับแบบฟองทุกประการ ส่วนขากลับก็เพียงกลับด้านของการเรียงลำดับแบบฟองนั่นเอง แต่การปรับปรุงดังนี้ก็ไม่ได้ทำให้ประสิทธิภาพในกรณีแย่ที่สุดดีกว่า O(n<sup>2</sup>) แต่อย่างใด
=== ตัวอย่างทีละขั้นตอน ===
การเรียงลำดับเลข 5 1 4 2 8 ในลิสต์ จากน้อยไปมาก ในแต่ละขั้นตอนตัวหนาหมายถึงตัวที่กำลังถูกเปรียบเทียบ<br />
'''รอบที่ 1'''<br />
( '''5''' '''1''' 4 2 8 ) <math>\to</math> ( '''1''' '''5''' 4 2 8 ), เปรียบเทียบตัวปัจจุบันกับตัวถัดไป สลับเนื่องจาก 5 > 1<br />
( 1 '''5''' '''4''' 2 8 ) <math>\to</math> ( 1 '''4''' '''5''' 2 8 ), สลับเนื่องจาก 5 > 4 <br />
( 1 4 '''5''' '''2''' 8 ) <math>\to</math> ( 1 4 '''2''' '''5''' 8 ), สลับเนื่องจาก 5 > 2 <br />
( 1 4 2 '''5''' '''8''' ) <math>\to</math> ( 1 4 2 '''5''' '''8''' ), ไม่สลับเนื่องจาก 5 ไม่มากกว่า 8<br />
'''รอบที่ 2'''<br />
( '''1''' '''4''' 2 5 8 ) <math>\to</math> ( '''1''' '''4''' 2 5 8 ) <br />
( 1 '''4''' '''2''' 5 8 ) <math>\to</math> ( 1 '''2''' '''4''' 5 8 ), สลับเนื่องจาก 4 > 2 <br />
( 1 2 '''4''' '''5''' 8 ) <math>\to</math> ( 1 2 '''4''' '''5''' 8 ) <br />
( 1 2 4 '''5''' '''8''' ) <math>\to</math> ( 1 2 4 '''5''' '''8''' ) <br />
ถึงแม้ว่าข้อมูลในลิสต์จะเรียงหมดแล้ว แต่ว่าก็ต้องตรวจสอบอีกครั้งหนึ่ง<br />
'''รอบที่ 3'''<br />
( '''1''' '''2''' 4 5 8 ) <math>\to</math> ( '''1''' '''2''' 4 5 8 ) <br />
( 1 '''2''' '''4''' 5 8 ) <math>\to</math> ( 1 '''2''' '''4''' 5 8 ) <br />
( 1 2 '''4''' '''5''' 8 ) <math>\to</math> ( 1 2 '''4''' '''5''' 8 ) <br />
( 1 2 4 '''5''' '''8''' ) <math>\to</math> ( 1 2 4 '''5''' '''8''' ) <br />
ในรอบนี้ไม่มีการสลับ แสดงว่าลำดับเลขเรียงจากน้อยไปมากแล้ว<br />
== การนำมาใช้งาน ==
=== ตัวอย่าง[[รหัสเทียม]] ===
<source lang="pascal">
begin bubbleSort ( A คือ แถวลำดับที่จะถูกเรียง )
do
ทำเครื่องหมายว่ายังไม่มีการสลับ
for i = 1 to ขนาดของ(A)-1
if A[i-1] > A[i] then
สลับ A[i-1] กับ A[i]
ทำเครื่องหมายว่ามีการสลับแล้ว
end if
end for
until ไม่มีการสลับแล้ว
end
</source>
=== การปรับปรุงประสิทธิภาพ ===
ในการเรียงลำดับจากน้อยไปมากเสร็จหนึ่งรอบจะทำให้ค่าที่มากที่สุดลำดับที่ i ไปอยู่ในตำแหน่งที่ n-1 ดังนั้นจึงสามารถมองข้ามตำแหน่งที่ n-1 ในการทำงานรอบต่อไปได้
<source lang="pascal">
begin bubbleSort ( A คือ แถวลำดับที่จะถูกเรียง )
n = ขนาดของ(A)
do
ทำเครื่องหมายว่ายังไม่มีการสลับ
for i = 1 to n-1
if A[i-1] > A[i] then
สลับ A[i-1] กับ A[i]
ทำเครื่องหมายว่ามีการสลับแล้ว
end if
end for
n = n - 1
until ไม่มีการสลับแล้ว
end
</source>
== ในการทำงานจริง ==
{{โครงส่วน}}
จะกล่าวได้ว่าการเรียงลำดับแบบฟองนั้นเป็นหนึ่งในขั้นตอนวิธีการเรียงลำดับที่ง่ายที่สุดเท่าที่เรารู้จัก ด้วย O(n<sup>2</sup>) ทำให้ประสิทธิภาพของมันลดลงอย่างมากแม้เราเพิ่มจำนวนสมาชิกที่จะเรียงเพียงเล็กน้อย แม้จะเปรียบเทียบขั้นตอนวิธีการเรียงลำดับที่มี O(n<sup>2</sup>) ด้วยกันนั้น[[การเรียงลำดับแบบแทรก]]ก็นับว่ามีประสิทธิภาพดีกว่าในกรณีทั่วๆ ไป แต่ด้วยความง่ายของขั้นตอนวิธีและความง่ายในการเขียนทำให้เราพบเห็นการเรียงลำดับแบบฟองได้อยู่ทั่วไป และมักจะได้เป็นขั้นตอนวิธีการเรียงลำดับแรกๆ ที่ผู้เริ่มเขียนโปรแกรมได้ศึกษานั่นเอง
== การเรียงรูปแบบอื่นที่แตกต่างออกไป ==
{{โครงส่วน}}
* [[Cocktail Sort]]
== การเรียกชื่อที่ผิด ==
{{โครงส่วน}}
== อ้างอิง ==
{{รายการอ้างอิง}}
| |||