Comb Sort ใน Java: ปรับปรุงจาก Bubble Sort

Comb Sort คืออะไร?

Comb Sort ปรับปรุงจาก Bubble Sort โดยใช้ Gap (ระยะห่าง) ที่ลดลงเรื่อยๆ (Shrink Factor 1.3) กำจัด "Turtles" (ค่าน้อยที่อยู่ท้าย) ได้เร็วกว่า

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

import java.util.Arrays; 

public class Demo { 
    void combSort(int[] arr) { 
        int gap = arr.length; 
        float shrink = 1.3f; 
        boolean swapped = false; 
        
        while (gap > 1 || swapped) { 
            // Update gap
            if (gap > 1) 
                gap = (int) (gap / shrink); 
            
            swapped = false; 
            
            // Compare-swap with gap
            for (int i = 0; i + gap < arr.length; i++) { 
                if (arr[i] > arr[i + gap]) { 
                    swap(arr, i, i + gap); 
                    swapped = true; 
                } 
            } 
        } 
    } 
    
    static void swap(int[] arr, int i, int j) { 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    } 
    
    public static void main(String args[]) { 
        Demo ob = new Demo(); 
        int[] arr = {6, 78, 90, -12, -45, 0, -1, 45}; 
        
        System.out.println("ก่อน: " + Arrays.toString(arr)); 
        ob.combSort(arr); 
        System.out.println("หลัง:  " + Arrays.toString(arr)); 
    } 
}

ผลลัพธ์

ก่อน: [6, 78, 90, -12, -45, 0, -1, 45]
หลัง:  [-45, -12, -1, 0, 6, 45, 78, 90]

คำอธิบาย

1. Gap เริ่มต้น = n (ความยาวอาร์เรย์)
2. Shrink factor = 1.3 (ค่าที่พิสูจน์ได้ว่า optimal)
3. Loop: จนกว่า gap=1 และไม่มีการ swap (เหมือน Bubble Sort รอบสุดท้าย)
4. Compare-swap: เปรียบเทียบ arr[i] กับ arr[i+gap] สลับถ้าผิดลำดับ

Trace (Gap Sequence)

n=8, shrink=1.3
gap: 8 -> 6 -> 4 -> 3 -> 2 -> 1 -> 1 (swapped) -> 1 (no swap) -> stop

ทำไม Shrink Factor = 1.3?

จากการทดลองเชิงประจักษ์ (Empirical) โดย Stephen Lacey และ Richard Box พบว่า 1.3 ให้ประสิทธิภาพดีที่สุด:

• < 1.3: Gap ลดช้าเกินไป → เยอะ passes
• > 1.3: Gap ลดเร็วเกินไป → ค้าง Turtles ไว้

ความซับซ้อน

เปรียบเทียบกับ Bubble Sort

ข้อควรระวัง

• ไม่ Stable
• ไม่ใช่ O(n log n) guaranteed (worst case O(n²))
• สำหรับ production ใช้ Arrays.sort() (TimSort/Dual-Pivot QuickSort)