Circle Sort Algorithm ใน C++

Circle Sort คืออะไร?

Circle Sort เป็น O(n log n) Sorting Algorithm ที่เปรียบเทียบ Element คู่ข้าม (Diametrically opposite) แบบ Recursive คล้าย Merge Sort แต่เปรียบเทียบ "ข้ามศูนย์กลาง"

หลักการทำงาน

1. เปรียบเทียบ Element แรกกับตัวสุดท้าย, ตัวที่ 2 กับตัวลำดับก่อนสุด, ...
2. ถ้าซ้าย > ขวา → Swap
3. แบ่ง Array เป็น 2 ครึ่ง ซ้ายและขวา → Recursive Circle Sort แต่ละครึ่ง
4. ทำซ้ำจนไม่มี Swap เกิดขึ้น (Array Sorted)

Visualization (n=6)

Initial: [2, 1, 5, 8, 7, 9]
Pass 1:  Compare (2,9) (1,7) (5,8) → Swap (1,7) → [2, 7, 5, 8, 1, 9]
         Left half [2,7,5]: Compare (2,5) → No swap
         Right half [8,1,9]: Compare (8,9) → No swap
Pass 2:  Compare (2,9) (7,1) (5,8) → Swap (7,1) → [2, 1, 5, 8, 7, 9]
         ... Continue until sorted
Final:   [1, 2, 5, 7, 8, 9]

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool circleSortRec(int* arr, int n) {
    bool swapped = false;
    
    if (n <= 2) {
        if (n == 2 && arr[0] > arr[1]) {
            swap(arr[0], arr[1]);
            swapped = true;
        }
        return swapped;
    }
    
    int mid = (n + 1) / 2;
    
    // Compare diametrically opposite pairs
    for (int i = 0; i < mid; i++) {
        int j = n - i - 1;
        if (i == j) { // Middle element (odd n)
            if (i + 1 < n && arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        } else if (arr[i] > arr[j]) {
            swap(arr[i], arr[j]);
            swapped = true;
        }
    }
    
    // Recurse on halves
    if (circleSortRec(arr, mid)) swapped = true;
    if (circleSortRec(arr + mid, n - mid)) swapped = true;
    
    return swapped;
}

void circleSort(int* arr, int n) {
    while (circleSortRec(arr, n)) {
        // Repeat until no swaps
    }
}

void printArray(int* arr, int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {2, 1, 7, 4, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original: ";
    printArray(arr, n);
    
    circleSort(arr, n);
    
    cout << "Sorted:   ";
    printArray(arr, n);
    
    // Test more cases
    int test1[] = {5, 4, 3, 2, 1};
    int test2[] = {1, 2, 3, 4, 5};
    int test3[] = {3, 1, 4, 1, 5, 9, 2, 6};
    
    circleSort(test1, 5);
    circleSort(test2, 5);
    circleSort(test3, 8);
    
    cout << "Test1: "; printArray(test1, 5);
    cout << "Test2: "; printArray(test2, 5);
    cout << "Test3: "; printArray(test3, 8);
    
    return 0;
}

Complexity

• Best: O(n log n) - Nearly sorted
• Average: O(n log n)
• Worst: O(n log n) - แต่ Constant factor ใหญ่กว่า Quick/Merge Sort
• Space: O(log n) - Recursion stack
• Stable: No - Swap ข้ามศูนย์กลางอาจเปลี่ยนลำดับ Equal elements
• In-place: Yes

เปรียบเทียบกับ Sort อื่นๆ

ผลลัพธ์

Original: 2 1 7 4 5 9
Sorted:   1 2 4 5 7 9
Test1: 1 2 3 4 5
Test2: 1 2 3 4 5
Test3: 1 1 2 3 4 5 6 9

สรุป

Circle Sort = Parallelizable Sorting Algorithm ใช้เปรียบเทียบ Diametric Pairs + Recursive Halves เน้นความ Parallel ได้ (เหมาะ GPU) แต่ใน CPU ใช้จริงน้อย เพราะ Constant Factor ใหญ่กว่า Quick/Merge Sort