ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบแทรก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
| บรรทัด 11: | บรรทัด 11: | ||
| optimal = No |
| optimal = No |
||
}} |
}} |
||
ในสาขา[[วิทยาการคอมพิวเตอร์]] '''การเรียงลำดับแบบแทรก''' ({{lang-en|insertion sort}}) เป็น[[ขั้นตอนวิธี]] |
|||
ในสาขา[[วิทยาการคอมพิวเตอร์]] '''การเรียงลำดับแบบแทรก''' ({{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> |
|||
=== ตัวอย่างรหัสเทียม === |
|||
<source lang="pascal"> |
|||
begin insertionSort ( A : list of sortable items ) |
|||
for i = 1 to length (A) - 1 |
|||
item = A[i] |
|||
cmpPos = i - 1 |
|||
while cmpPos >= 0 and item < A[cmpPos] |
|||
A[cmpPos + 1] = A[cmpPos] |
|||
cmpPos = cmpPos - 1 |
|||
end while |
|||
A[cmpPos + 1] = item |
|||
end for |
|||
end |
|||
</source> |
|||
[[หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ]] |
[[หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ]] |
||
รุ่นแก้ไขเมื่อ 16:23, 22 มกราคม 2562
 ตัวอย่างการเรียงลำดับแบบแทรกจากข้อมูลสุ่ม | |
| ประเภท | ขั้นตอนวิธีการเรียงลำดับ |
|---|---|
| โครงสร้างข้อมูล | รายการ |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
| ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | |
| ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
| ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | ใช้พื่นที่ เพิ่มเติม |
ในสาขาวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบแทรก (อังกฤษ: insertion sort) เป็นขั้นตอนวิธี
การเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแ