Counting Sort ใน Java: รองรับตัวเลขลบได้

Counting Sort คืออะไร?

Counting Sort เป็น Non-comparison Sorting นับความถี่ (Frequency) ของแต่ละค่า แล้วสร้างผลลัพธ์ เวลาสัมพันธ์กับช่วงค่า (Range) ไม่ใช่ n

เงื่อนไขใช้งาน

• ข้อมูลเป็น Integer (หรือ map ได้เป็น index)
• Range ของค่า (Max - Min) ไม่ใหญ่เกินไป
• Stable Sort

ตัวอย่างโค้ด (รองรับ Negative Numbers)

import java.util.*; 

public class Demo { 
    static void countingSort(int[] arr) { 
        if (arr == null || arr.length <= 1) return; 
        
        // หา min, max
        int max = Arrays.stream(arr).max().getAsInt(); 
        int min = Arrays.stream(arr).min().getAsInt(); 
        int range = max - min + 1; 
        
        int[] count = new int[range]; 
        int[] output = new int[arr.length]; 
        
        // 1. นับความถี่ (shift by -min เพื่อรองรับ negative)
        for (int num : arr) 
            count[num - min]++; 
        
        // 2. Prefix sum: count[i] = จำนวน elements ≤ i+min
        for (int i = 1; i < count.length; i++) 
            count[i] += count[i - 1]; 
        
        // 3. Build output (iterate backward เพื่อ stability)
        for (int i = arr.length - 1; i >= 0; i--) { 
            int idx = arr[i] - min; 
            output[count[idx] - 1] = arr[i]; 
            count[idx]--; 
        } 
        
        // 4. Copy back
        System.arraycopy(output, 0, arr, 0, arr.length); 
    } 
    
    static void printArray(int[] arr) { 
        System.out.println(Arrays.toString(arr)); 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10}; 
        
        System.out.println("ก่อน: "); 
        printArray(arr); 
        
        countingSort(arr); 
        
        System.out.println("หลัง Counting Sort: "); 
        printArray(arr); 
    } 
}

ผลลัพธ์

ก่อน: [-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10]
หลัง Counting Sort: [-95, -11, -5, -3, -1, 0, 8, 10, 34, 56, 89]

คำอธิบายขั้นตอน

1. Find Range: min=-95, max=89, range=185
2. Count Frequencies: count[value - min]++
3. Prefix Sum: count[i] = cumulative count → บอกตำแหน่งสุดท้ายของค่า i+min
4. Place Elements (Backward): ใส่ output ตาม count แล้วลด count → Stable
5. Copy Back

Trace สำหรับ arr = [4, 1, 3, 1] (min=1, max=4, range=4)

Count:     [2, 0, 1, 1]  (index 0=val1, 1=val2, 2=val3, 3=val4)
Prefix:    [2, 2, 3, 4]
Backward:
  i=3, val=1, idx=0, count[0]=2 -> output[1]=1, count[0]=1
  i=2, val=3, idx=2, count[2]=3 -> output[2]=3, count[2]=2
  i=1, val=1, idx=0, count[0]=1 -> output[0]=1, count[0]=0
  i=0, val=4, idx=3, count[3]=4 -> output[3]=4, count[3]=3
Output: [1, 1, 3, 4] ✓ Stable (1 ที่ index 1 อยู่ก่อน 1 ที่ index 0)

ความซับซ้อน

เมื่อไหร่ควรใช้

• n ใหญ่ แต่ range เล็ก (เช่น คะแนนสอบ 0-100, อายุ 0-120)
• ต้องการ Stable Sort
• Radix Sort ใช้ Counting Sort เป็น subroutine

ข้อจำกัด

• Range ใหญ่ (เช่น 32-bit int) → Memory ไม่พอ
• เฉพาะ Integer (หรือ mappable to integer)
• ไม่ใช่ Comparison Sort → ไม่ได้ใช้กับ Object ทั่วไป