C++의 원 정렬

Circle Sort는 주어진 요소 배열을 정렬하는 흥미로운 정렬 알고리즘입니다. 알고리즘은 배열의 요소를 정반대로 비교하고 한 부분의 요소가 정렬되면 배열의 다른 쪽 끝을 정반대로 계속 정렬합니다.

예

배열에 대한 원 정렬을 시각화해 보겠습니다. 6개의 요소가 있는 배열이 있다고 가정해 보겠습니다.

입력:

N = 6
arr [ ] = { 2, 1, 5, 8, 7, 9 }

각 배열 요소에 대해 동심원을 그리면 다음과 같이 나타납니다.

출력:

1 2 5 7 8 9

설명: Circle Sort를 사용하여 배열의 요소를 정렬하면 1, 2, 5, 7, 8, 9가 됩니다.

원 정렬 알고리즘

• 배열의 첫 번째 요소를 마지막 요소와 비교하고, 두 번째 요소를 배열의 두 번째 마지막 요소와 비교합니다.
• 이제 배열을 두 부분으로 분할한 다음 다시 원 정렬을 사용하여 전반부의 첫 번째 요소와 끝 부분을 비교합니다.
• 배열이 정렬될 때까지 1단계와 2단계를 재귀적으로 호출합니다.

원 정렬을 구현하는 C++ 프로그램

예시

#include <bits/stdc++.h>
using namespace std;
bool circle_sort_rec(int * arr, int n) {
   bool swaped = false;
   if (n <= 2) {
      if (arr[0] > arr[n - 1]) {
         swap(arr[0], arr[n - 1]);
         swaped = true;
      }
      return swaped;
   }
   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]);
            swaped = true;
         }
      } else {
         if (arr[i] > arr[n - i - 1]) {
            swap(arr[i], arr[n - i - 1]);
            swaped = true;
         }
      }
   }
   if (circle_sort_rec(arr, mid))
      swaped = true;
   if (circle_sort_rec(arr + mid, n - mid))
      swaped = true;
   return swaped;
}

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

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

출력

1 2 4 5 7