การเรียงลำดับแบบแทรก
จากวิกิพีเดีย สารานุกรมเสรี
การเรียงลำดับแบบแทรก (อังกฤษ: insertion sort) เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย ประสิทธิภาพ O(n2)
[แก้] ขั้นตอนวิธี
โดยการเรียงลำดับสมาชิก 2 ตัวแรกของแถว แล้วจากนั้นจึงเทียบสมาชิกตัวที่ 3 กับสมาชิก 2 ตัวแรก แล้วจึงแทรกเข้าไปในตำแหน่งที่เหมาะสม ทำจนกระทั่งสมาชิกครบทุกตัวจัดเรียงเสร็จสมบูรณ์
[แก้] ตัวอย่าง
ข้อมูล คือ 3 9 8 6 7
ครั้งที่ 1 [ (3 9) 8 6 7 ] --> [ 3 8 9 6 7 ] ; เนื่องจาก 3<8<9
ครั้งที่ 2 [ (3 8 9) 6 7] --> [ 3 6 8 9 7 ] ; เนื่องจาก 3<6<8<9
ครั้งที่ 3 [ (3 6 8 9) 7 ] --> [ 3 6 7 8 9 ] ; เนื่องจาก 3<6<7<8<9
ครั้งที่ 4 [ 3 6 7 8 9 ] --> [ 3 6 7 8 9 ] ; เนื่องจาก 3<6<7<8<9 เสร็จสมบูรณ์
