Bitonic Sort ใน Java: Parallel Sorting Algorithm

Bitonic Sort คืออะไร?

Bitonic Sort เป็นอัลกอริทึมเรียงลำดับแบบ Parallel เหมาะสำหรับ Hardware (GPU, FPGA) และ Parallel Computing ใช้ Bitonic Sequence (เพิ่มแล้วลด หรือ ลดแล้วเพิ่ม)

คุณสมบัติ

• Comparison pattern แบบคงที่ (Data-independent) - เหมาะสำหรับ parallel hardware
• Time Complexity: O(log² n) parallel steps
• Space: O(n log² n) comparators
• Stable: ไม่ Stable

ตัวอย่างโค้ด (Sequential Simulation)

public class Demo { 
    // Compare and swap ตาม direction
    void compareSwap(int[] arr, int i, int j, int direction) { 
        // direction=1: ascending, direction=0: descending
        if ((arr[i] > arr[j] && direction == 1) || 
            (arr[i] < arr[j] && direction == 0)) { 
            int temp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = temp; 
        } 
    } 
    
    // Merge bitonic sequence
    void bitonicMerge(int[] arr, int low, int cnt, int direction) { 
        if (cnt > 1) { 
            int k = cnt / 2; 
            for (int i = low; i < low + k; i++) 
                compareSwap(arr, i, i + k, direction); 
            bitonicMerge(arr, low, k, direction); 
            bitonicMerge(arr, low + k, k, direction); 
        } 
    } 
    
    // Build bitonic sequence then sort
    void bitonicSort(int[] arr, int low, int cnt, int direction) { 
        if (cnt > 1) { 
            int k = cnt / 2; 
            // Sort first half ascending
            bitonicSort(arr, low, k, 1); 
            // Sort second half descending
            bitonicSort(arr, low + k, k, 0); 
            // Merge whole sequence
            bitonicMerge(arr, low, cnt, direction); 
        } 
    } 
    
    static void printArray(int[] arr) { 
        for (int v : arr) System.out.print(v + " "); 
        System.out.println(); 
    } 
    
    public static void main(String args[]) { 
        int[] arr = {12, 67, 91, 54, 72, 32, 11, 0}; 
        int up = 1; // ascending
        
        Demo ob = new Demo(); 
        System.out.println("ก่อน: "); 
        printArray(arr); 
        
        ob.bitonicSort(arr, 0, arr.length, up); 
        
        System.out.println("หลัง Bitonic Sort: "); 
        printArray(arr); 
    } 
}

ผลลัพธ์

ก่อน: 
12 67 91 54 72 32 11 0 
หลัง Bitonic Sort: 
0 11 12 32 54 67 72 91

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

1. Bitonic Sequence: ลำดับที่เพิ่มขึ้นแล้วลดลง (หรือลดลงแล้วเพิ่มขึ้น)
2. bitonicSort: แบ่งครึ่ง เรียงครึ่งแรก ascending, ครึ่งหลัง descending → ได้ bitonic sequence → merge
3. bitonicMerge: Compare-swap ระหว่างคู่ที่ห่างกัน k แล้ว recursive merge ครึ่งๆ
4. compareSwap: สลับถ้าลำดับผิดตาม direction

Visualization (n=8)

Input:  [12, 67, 91, 54, 72, 32, 11, 0]

Stage 1: Build bitonic sequences of size 2
  [12,67]↑ [91,54]↓ [72,32]↑ [11,0]↓
  
Stage 2: Merge to size 4
  [12,54,67,91]↑ [0,11,32,72]↓
  
Stage 3: Merge to size 8 (final)
  [0,11,12,32,54,67,72,91]↑

Bitonic Sort vs อื่นๆ

เมื่อไหร่ใช้ Bitonic Sort

• Hardware implementation (Sorting networks)
• GPU Compute shaders
• Parallel programming coursework
• ไม่เหมาะ สำหรับ CPU sequential sorting ทั่วไป