Circle Sort in C++ (#1998)

Harikrishnan6336 · web-flow · commit e33d9f0f01f5 · 2021-06-01T17:36:47.000+05:30
* Create circle_sort.cpp

* Update readme.md
diff --git a/Algorithm/Searching_Sorting/readme.md b/Algorithm/Searching_Sorting/readme.md
@@ -63,6 +63,7 @@ Following are the types of searches which we will be discussing in this book.
 * Binary Search ----> [Python](/Code/Python/Binary_Search.py)
 * Book Allocation ----> [Java](/Code/Java/Book_Allocation.java)
 * Bucket Sort ----> [Java](/Code/Java/Bucket_Sort.java)
+* Circle Sort ----> [C++](/Code/C++/circle_sort.cpp)
 * Counting Sort ----> [C++](/Code/C++/couting_sort.cpp)
 * Cycle Sort ----> [C++](/Code/C++/cycle_sort.cpp)
 * DNF SORT ----> [C++](Algorithm/Searching_Sorting/dnf_sort.cpp)
diff --git a/Code/C++/circle_sort.cpp b/Code/C++/circle_sort.cpp
@@ -0,0 +1,93 @@
+// C++ program to implement Circle  Sort
+
+#include<bits/stdc++.h> 
+using namespace std; 
+  
+/*
+Performs recursive circular swaps and returns true if atleast one swap occurs
+*/
+bool rec_sort(int arr[], int beg, int end) 
+{ 
+    bool isSwap = false; 
+  
+    // If concerned array is empty, Return
+    if (beg == end) 
+        return false; 
+  
+    // Storing the values of beg, end to later use in the recursive call
+    int begA, endA;
+    for(begA = beg, endA = end; begA < endA; begA++, endA--) 
+    { 
+        //Compares the first and last elements 
+        if (arr[begA] > arr[endA]) 
+        { 
+            swap(arr[begA], arr[endA]); 
+            isSwap = true; 
+        } 
+        
+    } 
+  
+    // If the array has odd number of elements
+    if (begA == endA) 
+        if (arr[begA] > arr[endA + 1]) 
+        { 
+            swap(arr[beg], arr[endA+1]); 
+            isSwap = true; 
+        } 
+  
+    int mid = (end - beg) / 2; 
+    bool isSwapA = rec_sort(arr, beg, beg+mid); 
+    bool isSwapB = rec_sort(arr, beg+mid+1, end); 
+  
+    return (isSwap || isSwapA || isSwapB); 
+} 
+
+void circle_sort(int arr[], int n) 
+{  
+    while (rec_sort(arr, 0, n-1)) 
+    {    
+        
+    } 
+} 
+  
+
+int main()
+{
+    int n;
+    cout<<"\nHow many numbers do you want to sort? ";
+    cin>>n;
+    int arr[n];
+
+    if (n <= 0)
+    {
+        cout<<"The array is Empty!!!";
+        return 0;
+    }
+    // Input the numbers to sort
+    cout<<"Enter the numbers: ";
+    for (int i = 0; i < n; i++)
+        cin>>arr[i];
+  
+    //Call the sort function 
+    circle_sort(arr,n);  
+
+    cout<<"The numbers in sorted order is: ";
+    // Print the sorted array
+    for (int i = 0; i < n; i++)
+        cout<<arr[i]<<" ";
+    cout<<endl;
+    return 0;
+}
+
+/*
+Time Complexity: O(n*log(n))
+Space Complexity: O(n)
+SAMPLE INPUT AND OUTPUT
+SAMPLE 1
+How many numbers do you want to sort? 5
+Enter the numbers: 1 3 5 2 4
+The numbers in sorted order is:  1  2  3  4  5
+SAMPLE 2
+How many numbers do you want to sort? 0
+The array is Empty!!!
+*/
