โปรแกรม C: Recursive Bubble Sort (แบบเบิลซอร์ตแบบเรียกซ้ำ)

Bubble Sort เป็นอัลกอริทึมจัดเรียงง่ายๆ ที่เปรียบเทียบค่าติดกัน และสลับที่กันถ้าลำดับผิด รอบแรกค่ามากสุดจะไปอยู่ท้าย รอบที่สองค่ามากอันดับสองไปอยู่ลำดับสองท้าย ทำซ้ำจนเรียบร้อย

อัลกอริทึม Bubble Sort (Iterative)

• int arr[5] = { 5,4,2,1,3 };
• Loop i = 0 ถึง n-1
• Loop j = 0 ถึง n-i-2
• ถ้า arr[j] > arr[j+1] ให้สลับ

Recursive Bubble Sort (แบบเรียกซ้ำ)

1. Base Case: ถ้าความยาวอาร์เรย์ = 1 ให้ return
2. วนลูปผ่านอาร์เรย์ 1 รอบ ย้ายค่ามากสุดไปท้าย
3. เรียกฟังก์ชันซ้ำด้วยความยาวลดลง 1 (ไม่ต้องตรวจสอบท้ายที่เรียงแล้ว)

ตัวอย่างการทำงาน

Input: Arr[] = { 5,7,2,3,1,4 }, length=6

Output: Sorted array: 1 2 3 4 5 7

First Pass:  5 7 2 3 1 4 → swap → 5 2 7 3 1 4 → swap → 5 2 3 7 1 4 → swap → 5 2 3 1 7 4 → swap → 5 2 3 1 4 7
Second Pass: 5 2 3 1 4 7 → swap → 2 5 3 1 4 7 → swap → 2 3 5 1 4 7 → swap → 2 3 1 5 4 7 → swap → 2 3 1 4 5 7
Third Pass:  2 3 1 4 5 7 → swap → 2 1 3 4 5 7 (no more swaps)
Fourth Pass: 2 1 3 4 5 7 → swap → 1 2 3 4 5 7 (sorted)

โค้ดโปรแกรม Recursive Bubble Sort

#include <stdio.h>

void recurBubbleSort(int arr[], int len) {
    int temp;
    if (len == 1) {
        return; // Base case
    }
    // One pass: bubble largest to end
    for (int i = 0; i < len - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    // Recursive call for remaining array
    recurBubbleSort(arr, len - 1);
}

int main() {
    int Arr[] = {21, 34, 20, 31, 78, 43, 66};
    int length = sizeof(Arr) / sizeof(Arr[0]);
    
    recurBubbleSort(Arr, length);
    
    printf("Sorted array: ");
    for (int i = 0; i < length; i++) {
        printf("%d ", Arr[i]);
    }
    return 0;
}

ผลลัพธ์

Sorted array: 20 21 31 34 43 66 78

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

• Time: O(n²) - เหมือน Iterative version
• Space: O(n) - เนื่องจาก Recursion Stack (Iterative ใช้ O(1))

หมายเหตุ: Recursive Bubble Sort เหมาะสำหรับการศึกษา ในการใช้งานจริงควรใช้ qsort() หรืออัลกอริทึมที่ดีกว่า (Quick Sort, Merge Sort)