Sắp xếp vòng tròn trong C ++

Circle Sort là một thuật toán sắp xếp thú vị để sắp xếp một mảng các phần tử nhất định. Thuật toán so sánh các phần tử của mảng theo đường kính và khi các phần tử trong một phần được sắp xếp, sau đó liên tục sắp xếp phần còn lại của mảng theo đường kính.

Ví dụ

Hãy để chúng tôi hình dung cách sắp xếp vòng tròn cho một mảng. Giả sử chúng ta có một mảng có 6 phần tử.

Đầu vào:

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

Khi chúng ta vẽ các vòng tròn đồng tâm cho mỗi phần tử mảng, thì nó sẽ xuất hiện như sau

Đầu ra:

1 2 5 7 8 9

Giải thích: Sau khi sắp xếp các phần tử trong mảng bằng cách sử dụng Circle Sort, nó sẽ là 1, 2, 5, 7, 8, 9.

Thuật toán sắp xếp theo vòng tròn

• So sánh phần tử đầu tiên của mảng với phần tử cuối cùng, phần tử thứ hai với phần tử cuối cùng thứ hai của mảng.
• Bây giờ hãy chia mảng thành hai nửa và sau đó sử dụng lại sắp xếp vòng tròn để so sánh phần tử đầu tiên của nửa đầu với phần tử cuối của nó.
• Gọi đệ quy Bước 1 và bước 2 cho đến khi mảng được sắp xếp.

Chương trình C ++ để triển khai sắp xếp theo vòng kết nối

Ví dụ

#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;
}

Đầu ra

1 2 4 5 7