คำถามเกี่ยวกับ Time Complexity ของ Insertion Sort ใน C++

Time Complexity ของ Insertion Sort

คำถามพิเศษ: อาร์เรย์รูปแบบ 6,5,8,7,10,9,... (สลับคู่)

อาร์เรย์: [6,5, 8,7, 10,9, ..., i, i-1]

ทุกคู่ (2k, 2k-1) ถูกสลับกัน

วิเคราะห์

Insertion Sort จะเปรียบเทียบและเลื่อนข้อมูล:

• i=1 (ค่า 5): เปรียบเทียบกับ 6 → swap 1 ครั้ง
• i=2 (ค่า 8): อยู่ที่ถูกต้องแล้ว → 0 ครั้ง
• i=3 (ค่า 7): เปรียบเทียบกับ 8 → swap 1 ครั้ง
• i=4 (ค่า 10): ถูกต้อง → 0 ครั้ง

รูปแบบ: ทุก index คี่ ใช้ 1 การเปรียบเทียบ/สลับ, index คู่ใช้ 0

รวม ≈ n/2 operations → O(n)

โค้ด Insertion Sort มาตรฐาน

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // เลื่อนข้อมูลที่มากกว่า key ไปขวา
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

สรุป

• Insertion Sort ดีที่สุดสำหรับข้อมูล "เกือบเรียงแล้ว" (Nearly sorted)
• รูปแบบสลับคู่เป็น Nearly sorted → O(n)
• Stable sort, In-place, Online algorithm
• เหมาะสำหรับ n เล็ก (< 50) หรือข้อมูลเกือบเรียง