Thuật toán Circle Sort trong C++

Circle Sort: thuật toán sắp xếp so sánh các phần tử theo đường kính (đối xứng qua tâm), sau đó đệ quy chia đôi mảng.

Ví dụ

Input: N=6, arr = {2, 1, 5, 8, 7, 9}

So sánh: arr[0] với arr[5], arr[1] với arr[4], arr[2] với arr[3]

Output: 1 2 5 7 8 9

Thuật toán

• So sánh đầu-cuối, thứ 2 - thứ 2 từ cuối...
• Chia mảng làm 2 nửa, áp dụng Circle Sort cho mỗi nửa
• Đệ quy cho đến khi mảng có 1-2 phần tử

Code C++

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

bool circle_sort_rec(int* arr, int n) {
    bool swapped = false;
    if (n <= 2) {
        if (arr[0] > arr[n-1]) { swap(arr[0], arr[n-1]); swapped = true; }
        return swapped;
    }
    int mid = (n + 1) / 2;
    for (int i = 0; i < mid; i++) {
        if (i == n - i - 1) {
            if (arr[i] > arr[i+1]) { swap(arr[i], arr[i+1]); swapped = true; }
        } else {
            if (arr[i] > arr[n-i-1]) { swap(arr[i], arr[n-i-1]); swapped = true; }
        }
    }
    if (circle_sort_rec(arr, mid)) swapped = true;
    if (circle_sort_rec(arr + mid, n - mid)) swapped = true;
    return swapped;
}

void circle_sort(int* arr, int size) {
    while (circle_sort_rec(arr, size)) {}
}

int main() {
    int size = 6;
    int arr[6] = {2, 1, 7, 4, 5, 9};
    circle_sort(arr, size);
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    return 0;
}

Kết quả

1 2 4 5 7 9