โครงสร้างข้อมูลและการเรียงลำดับการแทรกอัลกอริทึม
นี่คืออัลกอริธึมการเรียงลำดับตามการเปรียบเทียบในสถานที่ ที่นี่รายการย่อยจะได้รับการดูแลซึ่งเรียงลำดับเสมอ ตัวอย่างเช่นส่วนล่างของอาร์เรย์จะได้รับการจัดเรียง องค์ประกอบที่จะ 'แทรก' ในรายการย่อยที่จัดเรียงนี้ต้องหาตำแหน่งที่เหมาะสมจากนั้นจะต้องแทรกเข้าไปที่นั่น ดังนั้นชื่อinsertion sort.
อาร์เรย์ถูกค้นหาตามลำดับและรายการที่ไม่ได้เรียงลำดับจะถูกย้ายและแทรกลงในรายการย่อยที่เรียงลำดับ (ในอาร์เรย์เดียวกัน) อัลกอริทึมนี้ไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนของกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุดคือΟ (n 2 ) โดยที่n คือจำนวนรายการ
การเรียงลำดับการแทรกทำงานอย่างไร
เราใช้อาร์เรย์ที่ไม่ได้เรียงลำดับสำหรับตัวอย่างของเรา
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/unsorted_array.jpg)
การเรียงลำดับการแทรกจะเปรียบเทียบสององค์ประกอบแรก
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_1.jpg)
พบว่าทั้ง 14 และ 33 เรียงลำดับจากน้อยไปมากแล้ว ตอนนี้ 14 อยู่ในรายการย่อยที่จัดเรียง
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_2.jpg)
การเรียงลำดับการแทรกเลื่อนไปข้างหน้าและเปรียบเทียบ 33 กับ 27
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_3.jpg)
และพบว่า 33 ไม่อยู่ในตำแหน่งที่ถูกต้อง.
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_4.jpg)
มันสลับ 33 กับ 27 นอกจากนี้ยังตรวจสอบกับองค์ประกอบทั้งหมดของรายการย่อยที่เรียงลำดับ ที่นี่เราจะเห็นว่ารายการย่อยที่เรียงลำดับมีเพียงองค์ประกอบเดียว 14 และ 27 มีค่ามากกว่า 14 ดังนั้นรายการย่อยที่เรียงลำดับจะยังคงเรียงลำดับหลังจากการสลับ
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_5.jpg)
ตอนนี้เรามี 14 และ 27 ในรายการย่อยที่เรียงลำดับ ต่อไปจะเปรียบเทียบ 33 กับ 10
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_6.jpg)
ค่าเหล่านี้ไม่ได้เรียงตามลำดับ
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_7.jpg)
ดังนั้นเราจึงสลับมัน
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_8.jpg)
อย่างไรก็ตามการแลกเปลี่ยนทำให้ 27 และ 10 ไม่เรียงลำดับ
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_9.jpg)
ดังนั้นเราจึงแลกเปลี่ยนพวกเขาด้วย
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_10.jpg)
อีกครั้งเราพบ 14 และ 10 ในลำดับที่ไม่เรียงลำดับ
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_11.jpg)
เราเปลี่ยนใหม่อีกครั้ง เมื่อสิ้นสุดการทำซ้ำครั้งที่สามเรามีรายการย่อยที่จัดเรียงไว้ 4 รายการ
![](https://post.nghiatu.com/assets/tutorial/data_structures_algorithms/images/insertion_sort_12.jpg)
กระบวนการนี้จะดำเนินต่อไปจนกว่าจะครอบคลุมค่าที่ไม่ได้เรียงลำดับทั้งหมดในรายการย่อยที่เรียงลำดับ ตอนนี้เราจะเห็นลักษณะการเขียนโปรแกรมบางส่วนของการเรียงลำดับการแทรก
อัลกอริทึม
ตอนนี้เรามีภาพรวมที่ใหญ่ขึ้นว่าเทคนิคการเรียงลำดับนี้ทำงานอย่างไรดังนั้นเราจึงสามารถหาขั้นตอนง่ายๆที่เราสามารถบรรลุการเรียงลำดับการแทรกได้
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
รหัสเทียม
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure
หากต้องการทราบข้อมูลเกี่ยวกับการแทรกการดำเนินงานการจัดเรียงในโปรแกรมภาษา C โปรดคลิกที่นี่