การเรียงลำดับการแทรกเป็นวิธีง่ายๆ ในการเรียงลำดับอาร์เรย์ ในเทคนิคนี้ อาร์เรย์จะถูกแบ่งออกเป็นส่วนที่เรียงลำดับและไม่เรียงลำดับ มีการหยิบองค์ประกอบจากส่วนที่ไม่ได้จัดเรียงและวางไว้ในตำแหน่งที่ถูกต้องในส่วนที่จัดเรียง
-
อิลิเมนต์อาร์เรย์ข้ามจาก 1 ถึง n
-
หากองค์ประกอบอาร์เรย์ที่ตำแหน่ง i มากกว่ารุ่นก่อน ก็ไม่จำเป็นต้องย้าย
-
หากองค์ประกอบอาร์เรย์ที่ตำแหน่ง i น้อยกว่ารุ่นก่อน จะต้องเลื่อนไปทางซ้ายจนกว่าเราจะพบรุ่นก่อนหน้าที่เล็กกว่าหรือหากเราไปถึงตำแหน่งซ้ายสุดในอาร์เรย์
ตัวอย่าง
เราสามารถเข้าใจแนวคิดข้างต้นได้ชัดเจนยิ่งขึ้นด้วยความช่วยเหลือจากตัวอย่าง สมมติว่าเรามีอาร์เรย์ต่อไปนี้ -
| 4 | 6 | 1 | 7 | 2 | 5 |
เราต้องเริ่มสำรวจอาร์เรย์จากดัชนี 1 (เพราะดัชนี 0 ไม่มีรุ่นก่อน)
ที่ดัชนี 1 −
6 นั้นยิ่งใหญ่กว่ารุ่นก่อน จึงไม่ต้องทำอะไรเลย
| 4 | 6 | 1 | 7 | 2 | 5 |
ที่ดัชนี 2 −
| 4 | 6 | 1 | 7 | 2 | 5 |
1 น้อยกว่ารุ่นก่อน ดังนั้นเราจึงจำเป็นต้องเลื่อนไปทางซ้าย เว้นแต่เราจะพบรุ่นก่อนหน้าที่เล็กกว่าหรือว่าเราไปถึงดัชนี 0 ในกรณีนี้ เราจะไปถึงดัชนี 0
| 4 | 6 | 1 | 7 | 2 | 5 |
ที่ดัชนี 3 −
| 1 | 4 | 6 | 7 | 2 | 5 |
ที่ดัชนี 4 −
| 1 | 4 | 6 | 7 | 2 | 5 |
เลื่อน 2 ไปทางซ้าย จนกว่าเราจะพบรุ่นก่อนหน้าที่น้อยกว่า 2
| 1 | 2 | 4 | 6 | 7 | 5 |
ที่ดัชนี 5 −
| 1 | 2 | 4 | 6 | 7 | 5 |
เลื่อน 5 ไปทางซ้าย จนกว่าเราจะพบรุ่นก่อนหน้าที่น้อยกว่า 5
| 1 | 2 | 4 | 5 | 6 | 7 |
ดังนั้นเราจึงได้รับอาร์เรย์ที่จัดเรียง
การเรียงลำดับการแทรกเป็นอัลกอริธึมการจัดเรียงแบบแทนที่ด้วยความซับซ้อนของเวลา O(n^2) และความซับซ้อนของพื้นที่ O(1)
ตัวอย่าง
def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] #get each element j = i-1 while j >= 0 and key &lit; arr[j] : #keep shifting until reaching index 0 or getting an element smaller than key arr[j + 1] = arr[j] j=j-1 arr[j + 1] = key arr = [4,6,1,7,2,5] insertionSort(arr) for i in range(len(arr)): print (arr[i],end=" ")
ผลลัพธ์
1 2 4 5 6 7
