การ Implement Insertion Sort ใน JavaScript

Insertion Sort

Simple Comparison Sort O(n²) เหมาะสำหรับ Small Arrays หรือ Nearly Sorted Data เนื่องจาก Low Overhead และ Adaptive

Algorithm

1. เริ่มจาก Index 1 (ถือว่า Index 0 Sorted แล้ว)
2. Key = Current Element
3. เปรียบเทียบกับ Sorted Part (ซ้ายมือ) ย้าย Element ที่มากกว่า Key ไปขวา
4. Insert Key ที่ตำแหน่งที่ถูกต้อง
5. Repeat จนครบทุก Element

Implementation

<script>
  function insertionSort(array) {
    const arr = [...array]; // Copy for Immutable
    
    for (let i = 1; i < arr.length; i++) {
      const key = arr[i];
      let j = i - 1;
      
      // Move elements > key to right
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
    return arr;
  }
  
  console.log(insertionSort([0, -3, 5, 8, 2, 7, 6]));
  // [-3, 0, 2, 5, 6, 7, 8]
</script>

Step-by-Step Trace

Initial:  [0, -3, 5, 8, 2, 7, 6]
i=1: Key=-3 → [-3, 0, 5, 8, 2, 7, 6]
i=2: Key=5  → [-3, 0, 5, 8, 2, 7, 6] (No shift)
i=3: Key=8  → [-3, 0, 5, 8, 2, 7, 6] (No shift)
i=4: Key=2  → [-3, 0, 2, 5, 8, 7, 6]
i=5: Key=7  → [-3, 0, 2, 5, 7, 8, 6]
i=6: Key=6  → [-3, 0, 2, 5, 6, 7, 8]

Complexity

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

• Small Array (< 50 elements)
• Nearly Sorted Data
• Online Algorithm (Streaming Data)
• Hybrid Sort (Timsort ใช้ Insertion Sort สำหรับ Run เล็กๆ)