Insertion Sort คืออะไร
Insertion Sort เป็นอัลกอริทึมจัดเรียงง่ายๆ แบ่ง array เป็นส่วนที่เรียงแล้ว (sorted) และยังไม่ได้เรียง (unsorted) นำ element จาก unsorted ไปวางตำแหน่งที่ถูกต้องใน sorted
ขั้นตอนการทำงาน
- วนลูป i จาก 1 ถึง n-1
- เก็บ key = arr[i]
- เปรียบเทียบ key กับ elements ด้านซ้าย (j = i-1, i-2, ...)
- เลื่อน elements ที่มากกว่า key ไปทางขวา
- วาง key ที่ตำแหน่งที่ถูกต้อง
ตัวอย่างขั้นตอน
Array: [4, 6, 1, 7, 2, 5]
- i=1: 6 > 4 ไม่ต้องย้าย
- i=2: 1 < 6,4 → เลื่อน 6,4 ไปขวา → [1, 4, 6, 7, 2, 5]
- i=3: 7 > 6 ไม่ต้องย้าย
- i=4: 2 < 7,6,4 → เลื่อน → [1, 2, 4, 6, 7, 5]
- i=5: 5 < 7,6 → เลื่อน → [1, 2, 4, 5, 6, 7]
Complexity
- Time: O(n²) worst/average, O(n) best (already sorted)
- Space: O(1) in-place
- Stable: รักษาลำดับของค่าเท่ากัน
โค้ด Python
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [4, 6, 1, 7, 2, 5]
insertionSort(arr)
print(arr) # [1, 2, 4, 5, 6, 7]เมื่อไหร่ควรใช้
- ข้อมูลน้อย (n < 50)
- ข้อมูลเรียงบางส่วนแล้ว (near sorted)
- ต้องการ stable sort
- Memory จำกัด (in-place)
