recursive algorithms help C++ programming: question : Create an ADT that contain

Question

recursive algorithms help C++ programming:

question: Create an ADT that contains a fixed-size array that holds 20 integers (i.e., int array[20]; ) and the following member functions:

A default constructor that initializes all the elements in this array to 20 random numbers (you can call the rand() function to generate a pseudo-random number).

A member function that recursively searches the largest number in the array. This function will return the value of the largest number.

A member function that recursively finds the value of the k-th smallest number in the array, where k is provided by the end-user. You are required to use the partition-based, recursive algorithm.

A member function that implements the recursive QuickSort algorithm to sort the array in increasing order.

You are required to use separate compilation. Specifically, your project will contain one header file, one .cpp file that implements all the member functions, and another .cpp file that contains the main() function. In the main() function, you will include test cases to call and test all your recursive functions.

Explanation / Answer

please refer below code

1) create ADT_max_min.h and paste below code

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

class ADT
{
public:
int array[20];
ADT();
int largest_recursive(int *array, int Size);
int k_th_smallest(int *array, int l,int r, int k);
};

2) Create ADT_max_min.cpp and paste below code

#include "ADT_max_min.h"

ADT::ADT()
{
srand(time(NULL));
for(int i = 0; i < 20; i++)
array[i] = rand() % 100;

for(int i = 0; i < 20; i++)
cout<<array[i]<<" ";

cout<<endl<<endl;

}
int max(int n1, int n2)
{
return n1 > n2 ? n1:n2;
}
int ADT::largest_recursive(int *array,int Size)
{
if(Size == 1)
return array[0];

return max(largest_recursive(array, Size-1), array[Size-1]);
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it
// and greater elements to right
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]);
return i;
}
int ADT::k_th_smallest(int *array, int l,int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around last element and get
// position of pivot element in sorted array
int pos = partition(array, l, r);

// If position is same as k
if (pos-l == k-1)
return array[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return k_th_smallest(array, l, pos-1, k);

// Else recur for right subarray
return k_th_smallest(array, pos+1, r, k-pos+l-1);
}

// If k is more than number of elements in array
return INT_MAX;
}

3) main.cpp

#include "ADT_max_min.h"

int main()
{
ADT A;
int large,k,kth_snall;
large = A.largest_recursive(A.array,20);
cout<<"Largest element is "<<large<<endl;

cout<<"Enter k for smallest number :"<<endl;
cin>>k;

kth_snall = A.k_th_smallest(A.array,0,19,k);
cout<<k<<"-th smallest element is : "<<kth_snall<<endl;
return 0;

}

please refer below output

50 5 30 80 79 49 75 45 49 39 45 62 92 54 87 32 71 30 24 52

Largest element is 92
Enter k for smallest number :
1
1-th smallest element is : 5

Process returned 0 (0x0) execution time : 5.714 s
Press any key to continue.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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