Insertion Sort ใน C#

ภาพรวม

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

เหมาะสำหรับ: ข้อมูลขนาดเล็ก, ข้อมูลที่ใกล้จะเรียงแล้ว (nearly sorted), หรือเป็นส่วนประกอบของอัลกอริทึมขั้นสูง (เช่น Timsort, Introsort)

ตัวอย่างโปรแกรม

using System;

namespace InsertionSortDemo
{
    class Example
    {
        static void Main(string[] args)
        {
            int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
            int n = 10, i, j, val, flag;
            
            Console.WriteLine("Insertion Sort");
            Console.Write("อาร์เรย์เริ่มต้น: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            // Insertion Sort
            for (i = 1; i < n; i++)
            {
                val = arr[i];     // ค่าที่จะแทรก
                flag = 0;
                
                // เลื่อนค่าที่มากกว่า val ไปทางขวา
                for (j = i - 1; j >= 0 && flag != 1; )
                {
                    if (val < arr[j])
                    {
                        arr[j + 1] = arr[j];
                        j--;
                        arr[j + 1] = val;
                    }
                    else
                        flag = 1; // พบตำแหน่งที่ถูกต้อง
                }
            }
            
            Console.Write("\nอาร์เรย์ที่จัดเรียงแล้ว: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

ผลลัพธ์

Insertion Sort
อาร์เรย์เริ่มต้น: 23 9 85 12 99 34 60 15 100 1
อาร์เรย์ที่จัดเรียงแล้ว: 1 9 12 15 23 34 60 85 99 100

การทำงานแบบทีละขั้นตอน

1. เริ่มต้น

int[] arr = { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
// ส่วนที่จัดเรียงแล้ว: [23] | ส่วนที่ยังไม่: [9, 85, 12, ...]

2. ลูปหลัก (Outer Loop)

for (i = 1; i < n; i++)
{
    val = arr[i];  // เอาค่าถัดไปมาแทรก
    // ... แทรก val ลงใน arr[0..i-1] ที่จัดเรียงแล้ว
}

3. ลูปใน (Inner Loop) - การแทรก

for (j = i - 1; j >= 0 && flag != 1; )
{
    if (val < arr[j])      // val น้อยกว่า -> เลื่อน arr[j] ไปขวา
    {
        arr[j + 1] = arr[j];
        j--;
        arr[j + 1] = val;  // วาง val ในช่องที่ว่าง
    }
    else
        flag = 1;          // val >= arr[j] -> พบตำแหน่ง หยุด
}

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

ข้อสังเกตสำคัญ

• Stable: รักษาลำดับของค่าเท่ากัน (ใช้ < ไม่ใช่ <=)
• In-place: ใช้พื้นที่ O(1)
• Online: สามารถจัดเรียงข้อมูลที่มาแบบสตรีมได้
• เร็วที่สุดสำหรับข้อมูลเล็ก (n < 50) หรือข้อมูล Nearly Sorted
• ใช้เป็น Base case ใน Timsort (Python, Java) และ Introsort (.NET)

เวอร์ชันมาตรฐาน (Standard Version)

public static void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; 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; // แทรก key
    }
}

เวอร์ชันนี้ชัดเจนกว่า: ใช้ key แทน val, ใช้ while แทน for+flag, และวาง key แค่ครั้งเดียวหลังลูปจบ