StoogeSort(A[0 ... n - 1]) if n = 2 and A[0] > A[1] swap A[0] and A[1] else if n
ID: 3911160 • Letter: S
Question
StoogeSort(A[0 ... n - 1])
if n = 2 and A[0] > A[1]
swap A[0] and A[1]
else if n > 2
m = ceiling(2n/3)
StoogeSort(A[0 ... m - 1])
StoogeSort(A[n - m ... n - 1])
Stoogesort(A[0 ... m - 1])
Implement STOOGESORT to sort an array/vector of integers.
Implement the algorithm in C++, your program should compile with g++ stoogesort.cpp.
Your program should be able to read inputs from a file called “data.txt” where the first value of each line is the number of integers that need to be sorted, followed by the integers. The output will be written to a file called “stooge.out”.
Explanation / Answer
The code will be
#include<iostream>
#include<cmath>
#include<fstream>
using namespace std;
void stoogeSort(int arr[],int n)
{
if(n==2 && arr[0]>arr[1])
swap(arr[0],arr[1]);
else if(n>2)
{
int m=ceil((2*n)/3.0);
stoogeSort(arr,m);
stoogeSort(arr+n-m,m);
stoogeSort(arr,m);
}
}
int main()
{
fstream f;
f.open("data.txt");
ofstream out;
out.open("stooge.out");
int n;
while(!f.eof())
{
f>>n;
int arr[n];
for(int i=0;i<n;i++)f>>arr[i];
stoogeSort(arr,n);
for(int i=0;i<n;i++)
out<<arr[i]<<" ";
out<<" ";
}
}