Insertion Sort (การจัดเรียงแบบแทรก)

Insertion Sort เป็นอัลกอริทึมจัดเรียงที่ง่ายและเข้าใจง่าย ทำงานคล้ายการจัดเรียงไพ่บนมือ: หยิบไพ่แต่ละใบ แล้วแทรกเข้าไปในตำแหน่งที่ถูกต้องในส่วนที่เรียงแล้ว

ความซับซ้อน (Complexity)

Space Complexity: O(1) (In-place)

แนวคิดการทำงาน

1. เริ่มจาก index 1 (องค์ประกอบที่ 2)
2. เก็บค่าปัจจุบันเป็น key
3. เปรียบเทียบกับองค์ประกอบทางซ้าย (ส่วนที่เรียงแล้ว)
4. เลื่อนองค์ประกอบที่มากกว่า key ไปทางขวา
5. วาง key ในช่องว่างที่เกิดขึ้น
6. ทำซ้ำจนครบทุกองค์ประกอบ

ตัวอย่างข้อมูล

Input:  9 45 23 71 80 55
Output: 9 23 45 55 71 80

อัลกอริทึม (Pseudocode)

insertionSort(array, size)
  for i = 1 to size-1:
    key = array[i]
    j = i - 1
    while j >= 0 AND array[j] > key:
      array[j + 1] = array[j]
      j = j - 1
    array[j + 1] = key

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void insertionSort(int *array, int size) {
    for (int i = 1; i < size; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    insertionSort(arr, n);
    cout << "After: "; display(arr, n);
}

คุณสมบัติสำคัญ

• Stable: รักษาลำดับค่าเท่ากัน
• In-place: ไม่ต้องการพื้นที่เพิ่ม
• Adaptive: เร็วขึ้นถ้าข้อมูลเรียงแล้วบางส่วน (Best case O(n))
• Online: สามารถจัดเรียงข้อมูลที่เข้ามาใหม่ทีละตัวได้

เมื่อไหร่ควรใช้ Insertion Sort?

• ข้อมูลเล็ก (n < 50)
• ข้อมูลเรียงแล้วเกือบหมด (Nearly sorted)
• ต้องการ Stable Sort
• หน่วยความจำจำกัด (In-place)
• เป็นส่วนประกอบของ Hybrid Sort (เช่น Timsort, Introsort)

การปรับปรุง: Binary Insertion Sort

ใช้ Binary Search หาตำแหน่งแทรก แทน Linear Search ลดการเปรียบเทียบเป็น O(log n) แต่วันที่ย้ายยังคงเป็น O(n²)