โปรแกรม Shell Sort ใน C#

ภาพรวม

Shell Sort เป็นอัลกอริทึมการจัดเรียงที่เป็นการปรับปรุงจาก Insertion Sort โดยอนุญาตให้แลกเปลี่ยนองค์ประกอบที่ห่างกันไกล (far apart) ก่อน แล้วค่อยๆ ลดช่องว่าง (gap) ลงเรื่อยๆ จนเหลือ 1 ซึ่งจะกลายเป็น Insertion Sort ธรรมดา วิธีนี้ลดจำนวนการเลื่อนข้อมูลได้มาก ทำให้เร็วกว่า Insertion Sort ธรรมดาอย่างมีนัยสำคัญ โดยเฉพาะสำหรับข้อมูลขนาดกลาง

อัลกอริทึมนี้ได้รับการเผยแพร่โดย Donald Shell ในปี 1959

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

using System;

namespace ShellSortDemo
{
    public class Example
    {
        static void ShellSort(int[] arr, int n)
        {
            int i, j, gap, temp;
            gap = 3; // เริ่มต้น gap = 3
            
            while (gap > 0)
            {
                for (i = 0; i < n; i++)
                {
                    j = i;
                    temp = arr[i];
                    
                    // เลื่อนองค์ประกอบที่มากกว่า temp ไปทางขวา
                    while ((j >= gap) && (arr[j - gap] > temp))
                    {
                        arr[j] = arr[j - gap];
                        j = j - gap;
                    }
                    arr[j] = temp;
                }
                
                // ลด gap ลงตามลำดับ: 3 -> 1 -> 0
                if (gap / 2 != 0)
                    gap = gap / 2;
                else if (gap == 1)
                    gap = 0;
                else
                    gap = 1;
            }
        }
        
        static void Main(string[] args)
        {
            int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
            int n = arr.Length;
            int i;
            
            Console.WriteLine("Shell Sort");
            Console.Write("อาร์เรย์เริ่มต้น: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            ShellSort(arr, n);
            
            Console.Write("\nอาร์เรย์ที่จัดเรียงแล้ว: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

ผลลัพธ์

Shell Sort
อาร์เรย์เริ่มต้น: 56 12 99 32 1 95 25 5 100 84
อาร์เรย์ที่จัดเรียงแล้ว: 1 5 12 25 32 56 84 95 99 100

การทำงานของอัลกอริทึม

1. การเริ่มต้น (Initialization)

int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
int n = arr.Length;
ShellSort(arr, n);

2. ฟังก์ชัน ShellSort() - โครงสร้างหลัก

static void ShellSort(int[] arr, int n)
{
    int i, j, gap, temp;
    gap = 3; // เริ่ม gap ที่ 3 (ประมาณ n/3)
    
    while (gap > 0)
    {
        // Insertion sort แบบมี gap
        for (i = 0; i < n; i++)
        {
            j = i;
            temp = arr[i];
            while ((j >= gap) && (arr[j - gap] > temp))
            {
                arr[j] = arr[j - gap];
                j = j - gap;
            }
            arr[j] = temp;
        }
        
        // ลด gap: 3 -> 1 -> 0 (จบ)
        if (gap / 2 != 0)
            gap = gap / 2;
        else if (gap == 1)
            gap = 0;
        else
            gap = 1;
    }
}

ลำดับ Gap (Gap Sequence)

ตัวอย่างนี้ใช้ลำดับ: 3, 1 (Shell's original sequence: n/2, n/4, ..., 1)

ลำดับ Gap ยอดนิยมอื่นๆ:

• Knuth: 1, 4, 13, 40, ... (h = 3h + 1)
• Sedgewick: 1, 5, 19, 41, 109, ...
• Ciura: 1, 4, 10, 23, 57, 132, 301, 701 (ดีที่สุดในทางปฏิบัติ)

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

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

• Shell Sort เป็น in-place sorting (ไม่ต้องการหน่วยความจำเพิ่ม)
• ไม่เสถียร (unstable) - องค์ประกอบที่เท่ากันอาจสลับตำแหน่งกัน
• เหมาะสำหรับข้อมูลขนาดกลาง (ไม่ถึงหลายพันรายการ)
• ในทางปฏิบัติ ใช้ Array.Sort() (Introsort) แทน จะเร็วและน่าเชื่อถือกว่า