C++ in Xcode Required Classes and Methods NOT functions. Programmers must apply

Question

C++ in Xcode

Required Classes and Methods NOT functions.

Programmers must apply coding conventions for code block indentation, comments describing methods/classes, white space between code blocks, and variable/method/class naming conventions.

Implement Inheritance, Getters, Setters, and other OOP tools as needed.

Create 2 int arrays. Array1[1000] and Array2[100000]

Create methods to fill the array with random integers

Create methods that will perform a linear search on the arrays for a key value entered by the user.

Create and implement a Bubble Sort Algorithm method that can be called to sort the given arrays.

Create and implement a Insertion Sort Algorithm method that can be called to sort the given arrays.

Create and implement a Recursive Quicksort Algorithm method that can be called to sort the given arrays.

Create a method to perform a binary search on a key value entered by the user.

Execute each method to demonstrate the methods and source code work.

Execute the Linear search methods on both arrays.

Execute the bubble sort, then binary search. (Make sure to randomize the array before the next step.)

Execute the Insertion sort, then binary search. (Make sure to randomize the array before the next step.)

Execute the Recursive Quicksort, then binary search. (Make sure to randomize the array before the next step.)

Attach source code and output.

Explanation / Answer

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
class Test
{
   public:
   int Array1[1000],Array2[100000];
   void randomise();
   void linearSearch(int a[]);
   void BinarySearch(int a[]);
   void bubbleSort(int a[],int n);
   void InsertionSort(int a[],int n);
   void QuickSort(int a[],int left,int right);
   void display();

};
void Test::randomise()
{
   int size1;
   srand(time(0));
size1=sizeof(Array1)/sizeof(Array1[0]);
   for(int i=0;i<size1;i++)
   {
               int radom_variable=rand()%1000+1;
       Array1[i]=radom_variable;
   }
   int size2;
size1=sizeof(Array2)/sizeof(Array2[0]);
   for(int i=0;i<size2;i++)
   {
       //srand(time(0));
       int radom=rand()%1000+1;
       Array2[i]=radom;
   }
}
void Test::display()
{
   for(int i=0;i<10;i++)
   {
       cout<<Array1[i]<<" ";
   }
}

void Test::bubbleSort(int a[],int n;)
{
   int i,j,temp;
   for(i=1;i<n;++i)
{
for(j=0;j<(n-i);++j)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
  
cout<<"Array after bubble sort:";
for(i=0;i<n;++i)
cout<<" "<<a[i];
}
void Test::InsertionSort(int a[],int n)
{
int i,temp,j;
for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;

while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j]; //moves element forward
j=j-1;
}

a[j+1]=temp; //insert element in proper place
}

cout<<" Sorted list is as follows ";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}

}
void Test::linearSearch(int a[])
{
   int i;
   cout<<"enter the key to serach";
   int searchKey,index,flag=1;
   cin>>searchKey;
   for(int i=0; i<10;i++)
   {
       if(searchKey==a[i])
       {
flag=0;
index=i;
       }
   }
   if(flag==0)
   {
       cout<<"key found at index :"<<index+1<<" ";
   }
   else
   {
       cout<<"key not found"<<" ";
   }
  
}
void QuickSort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}

int partition(int a[],int l,int u)
{
int v,i,j,temp;
v=a[l];
i=l;
j=u+1;
  
do
{
do
i++;
  
while(a[i]<v&&i<=u);
  
do
j--;
while(v<a[j]);
  
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
  
a[l]=a[j];
a[j]=v;
  
return(j);
}
void BinarySearch(int arr[])
{
cout<<"Enter a number to find :";
   int search,first,last,middle;
   cin>>search;
   first = 0;
   last = n-1;
   middle = (first+last)/2;
   while (first <= last)
   {
       if(arr[middle] < search)
       {
           first = middle + 1;

       }
       else if(arr[middle] == search)
       {
           cout<<search<<" found at location "<<middle+1<<" ";
           break;
       }
       else
       {
           last = middle - 1;
       }
       middle = (first + last)/2;
   }
   if(first > last)
   {
       cout<<"Not found! "<<search<<" is not present in the list.";
   }
}
int main(int argc, char const *argv[])
{
   Test obj;
   int size1=sizeof(obj.Array1)/sizeof(obj.Array1[0]);
   int size2=sizeof(obj.Array2)/sizeof(obj.Array2[0]);
   obj.randomise();
   //1.executing linear search on both arrays
   obj.linearSearch(obj.Array1);
   obj.linearSearch(obj.Array2);
   //randomising array's
   obj.randomise();
   //2.executing bubble sort then binary search
   obj.bubbleSort(obj.Array1,size1);
   obj.bubbleSort(obj.Array2,size2);
   obj.BinarySearch(obj.Array1);
   obj.BinarySearch(obj.Array2);
   //randomising array's
   obj.randomise();
   //3.executing insertion sort then binary search
   obj.InsertionSort(obj.Array1,size1);
   obj.InsertionSort(obj.Array2,size2);
   obj.BinarySearch(obj.Array1);
   obj.BinarySearch(obj.Array2);
   //randomising array's
   obj.randomise();
   //4.executing Quick sort then binary search
   obj.QuickSort(obj.Array1,size1);
   obj.QuickSort(obj.Array2,size2);
   obj.BinarySearch(obj.Array1);
   obj.BinarySearch(obj.Array2);

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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