การเรียงลำดับแบบแทรก
From Wikipedia, the free encyclopedia
ในสาขาวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบแทรก (อังกฤษ: insertion sort) เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง แน่นอนว่าในตอนเริ่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว ลักษณะเดียวกับการเรียงไพ่ในมือ และด้วยประสิทธิภาพ O(n2) ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงานในรายการที่มีจำนวนสมาชิกมากๆ ซึ่งขั้นตอนวิธีการเรียงลำดับซึ่งซับซ้อนกว่าเช่น การเรียงลำดับแบบเร็ว, การเรียงลำดับแบบผสาน, การเรียงลำดับแบบฮีป มีความเหมาะสมมากกว่า
ข้อมูลเบื้องต้น ประเภท, โครงสร้างข้อมูล ...
![]() ตัวอย่างการเรียงลำดับแบบแทรกจากข้อมูลสุ่ม | |
ประเภท | ขั้นตอนวิธีการเรียงลำดับ |
---|---|
โครงสร้างข้อมูล | รายการ |
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | ใช้พื่นที่ |
|
ปิด
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Insertion-sort-example-300px.gif/220px-Insertion-sort-example-300px.gif)