Assignment: 11 C++ data strucs and aglorithms. Please follow All instructions to

Question

Assignment: 11

C++ data strucs and aglorithms. Please follow All instructions to write this program. Required Classes and Methods NOT functions. To receive full credit, 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.)

Explanation / Answer

Answer

#include <iostream>
#include <string>
#include <cstdlib> /* srand, rand */
using namespace std;
class arraySort
{
public:
int arr1[1000],arr2[100000];
void fillARR1()
{
for(int i=0;i<1000;i++)
arr1[i]=rand()%100;
}
void fillARR2()
{
for(int i=0;i<100000;i++)
arr2[i]=rand()%100;
}
void linearSearch1(int key)
{
cout<<" ------------LINEAR SEARCH------------ ";
for(int i=0;i<1000;i++)
if(arr1[i]==key)
cout<<" "<<key<<" found at index "<<i;
}
void linearSearch2(int key)
{
cout<<" ------------LINEAR SEARCH------------ ";
for(int i=0;i<100000;i++)
if(arr2[i]==key)
cout<<" "<<key<<" found at index "<<i;
}
void bSearch1(int key)
{   
cout<<" ------------BINARY SEARCH------------ ";
int beg=1;
int end=1000;
int mid=(beg+end)/2; // Find Mid Location of Array
while(beg<=end && arr1[mid]!=key) // Compare Item and Value of Mid
{
if(arr1[mid]<key)
beg=mid+1;
else
end=mid-1;
mid=(beg+end)/2;
}
if(arr1[mid]==key)
cout<<" "<<key<<" found at "<<mid<<" index";
}
void bSearch2(int key)
{   
cout<<" ------------BINARY SEARCH------------ ";
int beg=1;
int end=100000;
int mid=(beg+end)/2; // Find Mid Location of Array
while(beg<=end && arr2[mid]!=key) // Compare Item and Value of Mid
{
if(arr2[mid]<key)
beg=mid+1;
else
end=mid-1;
mid=(beg+end)/2;
}
if(arr2[mid]==key)
cout<<" "<<key<<" found at "<<mid<<" index";
}
void bubbleSort1()
{
cout<<" ------------BUBBLE SORT------------ ";
for(int p=0;p<1000;p++) // Loop for Pass
{
for(int j=0;j<1000;j++)
{
if(arr1[p]<arr1[j])
{
int temp=arr1[p]; // Interchange Values
arr1[p]=arr1[j];
arr1[j]=temp;
}
}
}
}
void bubbleSort2()
{
cout<<" ------------BUBBLE SORT------------ ";
for(int p=0;p<100000;p++) // Loop for Pass
{
for(int j=0;j<100000;j++)
{
if(arr2[p]<arr2[j])
{
int temp=arr2[p]; // Interchange Values
arr2[p]=arr2[j];
arr2[j]=temp;
}
}
}
}
void insertionSort1()
{
cout<<" ------------INSERTION SORT------------ ";
int key,i,j;
for(j=1;j<1000;j++)
{
key=arr1[j];
i=j-1;
while((i>0)&&(arr1[i]>key))
{
arr1[i+1]=arr1[i];
i=i-1;
}
arr1[i+1]=key;
}
}
void insertionSort2()
{
cout<<" ------------INSERTION SORT------------ ";
int key,i,j;
for(j=1;j<100000;j++)
{
key=arr2[j];
i=j-1;
while((i>0)&&(arr2[i]>key))
{
arr2[i+1]=arr2[i];
i=i-1;
}
arr2[i+1]=key;
}
}
void quick1(int l,int u)
{
int p,temp;
if(l<u)
{
p=arr1[l];
int i=l;
int j=u;
while(i<j)
{
while(arr1[i] <= p && i<j )
i++;
while(arr1[j]>p && i<=j )
j--;
if(i<=j)
{
temp=arr1[i];
arr1[i]=arr1[j];
arr1[j]=temp;
}
}
temp=arr1[j];
arr1[j]=arr1[l];
arr1[l]=temp;
quick1(l,j-1);
quick1(j+1,u);
}
}
void quick2(int l,int u)
{
int p,temp;
if(l<u)
{
p=arr2[l];
int i=l;
int j=u;
while(i<j)
{
while(arr2[i] <= p && i<j )
i++;
while(arr2[j]>p && i<=j )
j--;
if(i<=j)
{
temp=arr2[i];
arr2[i]=arr2[j];
arr2[j]=temp;
}
}
temp=arr2[j];
arr2[j]=arr2[l];
arr2[l]=temp;
quick2(l,j-1);
quick2(j+1,u);
}
}
int Menu()
{
int choice;
cout<<" ------------ALGORITHUM MENU------------ ";
cout<<" 1. Linear search";
cout<<" 2. Binary search";
cout<<" 3. Bubble sort";
cout<<" 4. Insertion sort";
cout<<" 5. Recursive Quicksort";
cout<<" 6. Exit";
cout<<" ->. Enter your Choice : ";
cin>>choice;
return choice;
}
void display1()
{
cout<<" ------------------1000 Element Array------------------ ";
for(int i=1;i<=1000;i++)
{
cout<<" "<<arr1[i-1];
if(i%50==0)
cout<<endl;
}
}
void display2()
{
cout<<" ------------------100000 Element Array------------------ ";
for(int i=1;i<=100000;i++)
{
cout<<" "<<arr2[i-1];
if(i%50==0)
cout<<endl;
}
}
};
int main()
{
srand (time(NULL)); /* initialize random seed: */
arraySort obj;
int ch,choice,key;
do
{
cout<<" ------------ARRAY MENU------------ ";
cout<<" 1. 1000 Element Array";
cout<<" 2. 100000 Element Array";
cout<<" 3. Exit";
cout<<" ->Enter Choice : ";
cin>>ch;
if(ch==1)
{
choice=obj.Menu();
obj.fillARR1();
if(choice==1)
{
cout<<" Enter Key to Search : ";
cin>>key;
obj.linearSearch1(key);
}
else if(choice==2)
{
cout<<" Enter Key to Search : ";
cin>>key;
obj.bSearch1(key);
}
else if(choice==3)
{
obj.bubbleSort1();
obj.display1();
}
else if(choice==4)
{
obj.insertionSort1();
obj.display1();
}
else if(choice==5)
{
cout<<" ------------QUICKSORT SORT------------ ";
obj.quick1(0,1000);
obj.display1();
}
else if(choice==6)
{
break;
}
else
{
cout<<" Wrong Input..!! try Again ";
}
}
else if(ch==2)
{
choice=obj.Menu();
obj.fillARR2();
if(choice==1)
{
cout<<" Enter Key to Search : ";
cin>>key;
obj.linearSearch2(key);
}
else if(choice==2)
{
cout<<" Enter Key to Search : ";
cin>>key;
obj.bSearch2(key);
}
else if(choice==3)
{
obj.bubbleSort2();
obj.display2();
}
else if(choice==4)
{
obj.insertionSort2();
obj.display2();
}
else if(choice==5)
{
cout<<" ------------QUICKSORT SORT------------ ";
obj.quick2(0,100000);
obj.display2();
}
else if(choice==6)
{
break;
}
else
{
cout<<" Wrong Input..!! try Again ";
}
}
else if(ch==3)
{
break;
}
else
{
cout<<" Wrong Input..!! try Again ";
}
}while(ch!=3);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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