Implement the below STOOGESORT algorithm to sort an array/vector of integers. Im
ID: 3587857 • 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 <fstream>
using namespace std;
void stoogesort(int A[],int start, int end)
{
if (start >= end)
return;
if (A[start] > A[end]) {
int temp = A[start];
A[start] = A[end];
A[end] = temp;
}
// If there are more than 2 elements in
// the array
if(end - start + 1 > 2)
{
int t = (end - start + 1) / 3;
stoogesort(A, start, end - t);
stoogesort(A, start + t, end);
stoogesort(A, start, end - t);
}
}
int main()
{
ifstream input("data.txt");
int n;
input >> n;
int *arr = new int [n];
for (int i = 0; i < n; i++) {
input >> arr[i];
}
input.close();
stoogesort(arr, 0, n-1);
ofstream output("stooge.out");
for (int i = 0; i < n; i++) {
output << arr[i] << endl;
}
output.close();
delete [] arr;
return 0;
}