Implement the below STOOGESORT algorithm to sort an array/vector of integers. Im
ID: 3585872 • Letter: I
Question
Implement the below STOOGESORT algorithm to sort an array/vector of integers. Implement the algorithm in C++. The program must 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”.
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])
Explanation / Answer
#include <iostream>
#include <math.h>
#include <sstream>
#include <fstream>
using namespace std;
void StoogeSort(int A[],int start,int end){
if (end == 1 && A[0] > A[1]){
//swap A[0] and A[1]
int temp=A[0];
A[0]=A[1];
A[1]=temp;
}
else if (end > 1){
int m = ceil(2*(end+1)/3);
StoogeSort(A,0, m - 1);
StoogeSort(A,end - m +1,end);
StoogeSort(A,0 , m - 1);
}
}
int main()
{
string input;
ifstream data("data.txt");
while(getline(data,input)){
istringstream ss(input);
string token;
int n=0;
getline(ss, token, ',');
n=stoi(token);
int A[n];
int index=0;
while(getline(ss, token, ',')) {
A[index++]=stoi(token);
}
StoogeSort(A,0,n-1);
ofstream outfile;
outfile.open ("stooge.out");
for(int i=0;i<n-1;i++)
outfile << A[i] <<",";
outfile<<A[n-1]<<endl;
outfile.close();
}
return 0;
}