Recursive Bubble Sort ใน Java

Recursive Bubble Sort คืออะไร?

Bubble Sort แบบ Recursive: ผ่าน array วนลูปสลับค่าที่ผิดลำดับ (pass หนึ่ง) → ตัวมากที่สุดจะอยู่ท้าย → เรียก recursive กับ n-1 ตัวแรก

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

import java.util.Arrays; 

public class Demo { 
    static void bubbleSort(int[] arr, int n) { 
        // Base case
        if (n == 1) return; 
        
        // One pass: bubble largest to end
        for (int i = 0; i < n - 1; i++) { 
            if (arr[i] > arr[i + 1]) { 
                int temp = arr[i]; 
                arr[i] = arr[i + 1]; 
                arr[i + 1] = temp; 
            } 
        } 
        
        // Recursive call for remaining n-1 elements
        bubbleSort(arr, n - 1); 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {45, 67, 89, 31, 63, 0, 21, 12}; 
        
        System.out.println("ก่อน: " + Arrays.toString(arr)); 
        bubbleSort(arr, arr.length); 
        System.out.println("หลัง:  " + Arrays.toString(arr)); 
    } 
}

ผลลัพธ์

ก่อน: [45, 67, 89, 31, 63, 0, 21, 12] 
หลัง:  [0, 12, 21, 31, 45, 63, 67, 89]

คำอธิบาย

1. Base case: n == 1 → array ขนาด 1 เรียงแล้ว return
2. One pass: วน i=0 ถึง n-2 เปรียบเทียบ arr[i] กับ arr[i+1] สลับถ้าผิดลำดับ → หลัง pass ตัวมากที่สุดอยู่ index n-1
3. Recursive call: เรียก bubbleSort(arr, n-1) เพื่อเรียง n-1 ตัวแรก

Trace (arr = [5, 1, 4, 2])

bubbleSort(arr, 4)
  Pass 1: [1,4,2,5]  (5 bubbled to end)
  bubbleSort(arr, 3)
    Pass 2: [1,2,4]  (4 bubbled to end)
    bubbleSort(arr, 2)
      Pass 3: [1,2]  (2 bubbled to end)
      bubbleSort(arr, 1) -> return

ความซับซ้อน

* ไม่มี early termination flag เหมือน iterative version

การปรับปรุง: Early Termination

static void bubbleSortOptimized(int[] arr, int n) { 
    if (n == 1) return; 
    
    boolean swapped = false; 
    for (int i = 0; i < n - 1; i++) { 
        if (arr[i] > arr[i + 1]) { 
            swap(arr, i, i + 1); 
            swapped = true; 
        } 
    } 
    
    if (!swapped) return; // เรียงแล้ว หยุดก่อน
    bubbleSortOptimized(arr, n - 1); 
}

ข้อควรระวัง

• Recursive Bubble Sort ใช้ stack O(n) → อาจ StackOverflow หาก n ใหญ่
• Bubble Sort เองมีประสิทธิภาพแย่ O(n²) → ไม่ควรใช้จริง
• เหมาะสำหรับการศึกษา recursion pattern
• Java ใช้ Arrays.sort() (TimSort/Dual-Pivot QuickSort) แทนในทางปฏิบัติ