ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบแทรก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล ย้อนกลับไปรุ่น 8482908 วันที่ 2019-09-03 16:00:38 โดย 124.122.41.172 ด้วยป็อปอัพ |
|||
บรรทัด 12:
}}
ในสาขา[[วิทยาการคอมพิวเตอร์]] '''การเรียงลำดับแบบแทรก''' ({{lang-en|insertion sort}}) เป็น[[ขั้นตอนวิธี]]การเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง แน่นอนว่าในตอนเริ่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว ลักษณะเดียวกับการเรียงไพ่ในมือ และด้วยประสิทธิภาพ ''O(n<sup>2</sup>) '' ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงานในรายการที่มีจำนวนสมาชิกมากๆ ซึ่งขั้นตอนวิธีการเรียงลำดับซึ่งซับซ้อนกว่าเช่น [[การเรียงลำดับแบบเร็ว]], [[การเรียงลำดับแบบผสาน]], [[การเรียงลำดับแบบฮีป]] มีความเหมาะสมมากกว่า
== ขั้นตอนวิธี ==
=== ตัวอย่างทีละขั้นตอน4 ===
การเรียงลำดับข้อมูลในรายการดังนี้ 3 9 8 6 7 ด้วยขั้นตอนวิธีแบบแทรก เริ่มต้นด้วยข้อมูลทุกตัวยกเว้นตัวแรกยังไม่ได้เรียง ข้อมูลที่อยู่ในเครื่องหมาย (..) ถือว่าเป็นข้อมูลที่เรียงจากน้อยไปมากแล้ว<br />
'''ครั้งที่ 1'''<br>
[ (3) '''9''' 8 7 6 ] <math>\to</math> [ (3 '''9''') 8 7 6 ]<br>
'''ครั้งที่ 2'''<br>
[ (3 9) '''8''' 7 6 ] <math>\to</math> [ (3 9 '''8''') 7 6 ]<br>
[ (3 9 '''8''') 7 6 ] <math>\to</math> [ (3 '''8''' 9) 7 6 ]<br>
'''ครั้งที่ 3'''<br>
[ (3 8 9) '''7''' 6 ] <math>\to</math> [ (3 8 9 '''7''') 6 ]<br>
[ (3 8 9 '''7''') 6 ] <math>\to</math> [ (3 8 '''7''' 9) 6 ]<br>
[ (3 8 '''7''' 9) 6 ] <math>\to</math> [ (3 '''7''' 8 9) 6 ]<br>
'''ครั้งที่ 4'''<br>
[ (3 7 8 9) '''6''' ] <math>\to</math> [ (3 7 8 9 '''6''') ]<br>
[ (3 7 8 9 '''6''') ] <math>\to</math> [ (3 7 8 '''6''' 9) ]<br>
[ (3 7 8 '''6''' 9) ] <math>\to</math> [ (3 7 '''6''' 8 9) ]<br>
[ (3 7 '''6''' 8 9) ] <math>\to</math> [ (3 '''6''' 7 8 9) ]<br>
เรียงเสร็จเรียบร้อย<br>
=== ตัวอย่างรหัสเทียม ===
| |||