스투지 정렬을 수행하는 C++ 프로그램

Stooge Sort는 주어진 데이터를 정렬하는 데 사용됩니다. 재귀적 정렬 알고리즘입니다. Stooge Sort는 배열을 두 개의 겹치는 부분(각각 2/3)으로 나누고 I, II, 다시 I 부분을 정렬하여 3단계로 배열을 정렬합니다. 이 알고리즘의 최악의 시간 복잡도는 O(n^2.7095)입니다.

알고리즘

Begin
   Take input of data.
   Call StoogeSort() function with ‘a’ the array of data and ‘n’ the number of values, in the argument list.
   Implement Sorting using recursive approach.
   Divide the array into first 2/3 element as part I and last 2/3 as part II.
   Then send the first, second and again first part into StoogeSort().
   If the length is not further breakable then swap element at the start and end if a[end] < a[start].
   Return to main and display the result.
End.

예시 코드

#include<iostream>
using namespace std;
void StoogeSort(int a[],int start, int end) {
   int temp;
   if(end-start+1 > 2) {
      temp = (end-start+1)/3;
      StoogeSort(a, start, end-temp);
      StoogeSort(a, start+temp, end);
      StoogeSort(a, start, end-temp);
   }
   if(a[end] < a[start]) {
      temp = a[start];
      a[start] = a[end];
      a[end] = temp;
    }
}
int main() {
   int m, i;
   cout<<"\nEnter the number of data element to be sorted: ";
   cin>>m;
   int arr[m];
   for(i = 0; i < m; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>arr[i];
   }
   StoogeSort(arr, 0, m-1);
   cout<<"\nSorted Data ";
   for (i = 0; i < m; i++)
      cout<<"->"<<arr[i];
   return 0;
}

출력

Enter the number of data element to be sorted: 4
Enter element 1: 6
Enter element 2: 7
Enter element 3: 3
Enter element 4: 2
Sorted Data ->2->3->6->7