a) Implement the STOOGESORT algorith to sort an array of integers using C or C++

Question

a) Implement the STOOGESORT algorith to sort an array of integers using C or C++.  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”.

b) Modify the code from part a to collect running time data. Instead of reading arrays from a file to sort, you will now generate arrays of size n containing random integer values and then time how long it takes to sort the arrays.You will need at least seven values of t (time) greater than 0. If there is variability in the times between runs of the algorithm you may want to take the average time of several runs for each value of n. *(show the code modifications)

c) Plot the running time data you collected on an individual graph with n on the x-axis and time on the y-axis.

d) What type of curve best fits the StoogeSort data set? Give the equation of the curve that best “fits” the data and draw that curve on the graphs of created in part c). How does your experimental running time compare to the theoretical running time of the algorithm?

Explanation / Answer

Issue Description

1. Stooge sort is a recursive arranging calculation.

2. It separates the exhibit into two covering parts, 2/3 each.

3. Sort the cluster in three stages by arranging I then II and again I part.

4. It is genuinely wasteful calculation with most pessimistic scenario time intricacy O(n^2.7095).

Issue Solution

1. Recursively separate the partition the exhibit into two sections of size 2/3 of cluster length.

2. Sort the initial segment.

3. Sort second part.

4. Again sort the initial segment.

5. Show the outcome.

6. Exit.

Program/Source Code

C++ program to execute Shaker Sort.

This program is effectively keep running on Dev-C++ utilizing TDM-GCC 4.9.2 MinGW compiler on a Windows framework.

....#include<iostream>

using namespace std;

// A function implementing stooge sort.
void StoogeSort(int a[],int start, int end)
{
int temp;
// Further breaking the array if the Subpart's length is more than 2.
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);
}

// swapping the element at start and end.
if(a[end] < a[start])
{
  temp = a[start];
  a[start] = a[end];
  a[end] = temp;
}
}

int main()
{
int n, i;
cout<<" Enter the number of data element to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
  cout<<"Enter element "<<i+1<<": ";
  cin>>arr[i];
}

StoogeSort(arr, 0, n-1);

// Printing the sorted data.
cout<<" Sorted Data ";
for (i = 0; i < n; i++)
  cout<<"->"<<arr[i];

return 0;
}...

Program Explanation

1. Take contribution of information.

2. Call StoogeSort() work with 'arr' the variety of information and 'n' the quantity of qualities, in the contention list.

3. Actualize Sorting utilizing recursive approach.

4. Separation the cluster into initial 2/3 component as part I and last 2/3 as part II.

5. Send the primary, second and again initial segment into StoogeSort().

6. On the off chance that the length isn't further fragile at that point swap component toward the begin and end if a[end] < a[start].

7. Come back to fundamental and show the outcome.

8. Exit.

.....

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.