เรียงวงกลมในภาษา 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