C++ data strucs and aglorithms. Please follow instructions Required Classes and

Question

C++ data strucs and aglorithms. Please follow instructions

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

#include<iostream>
#include<conio.h>
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
using namespace std;

// this is swapping function
void swap(int* a, int* b){
       int t = *a;
       *a = *b;
       *b = t;
   }

/* This function takes last element as pivot,then it places the element in a correct position

*/
int Array_partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void Array_quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is Array_partitioning index, arr[p] is now
at right place */
int pi = Array_partition(arr, low, high);

// Separately sort elements before
// Array_partition and after Array_partition
Array_quickSort(arr, low, pi - 1);
Array_quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void display_Array(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<<arr[i]<<endl;

}
void random_array1(int rand_num_Array[]){
   int search_num;
   srand (time(NULL));

/* generate random number between 1 and 1000: */

for(int i=0;i<1000;i++){
  
rand_num_Array[i]=rand() % 1000 + 1;
}
cout<<"Random Numbers in Array:"<<endl;
for(int j=0;j<1000;j++){
   cout<<"Index at "<<"["<<j<<"] "<<rand_num_Array[j]<<endl;
}
cout<<"Enter Number to search in Array:";
cin>>search_num;
for(int i=0;i<1000;i++){
       if(rand_num_Array[i]==search_num){
           cout<<"Number is at"<<i<<endl;
           break;
       }
}

}

void random_array2(int rand_num_Array[]){
   int search_num;
   srand (time(NULL));

/* generate random number between 1 and 1000: */

for(int i=0;i<100000;i++){

rand_num_Array[i]=rand() % 100000 + 1;
}
cout<<"Random Numbers in Array:"<<endl;
for(int j=0;j<100000;j++){
   cout<<"Index at "<<"["<<j<<"] "<<rand_num_Array[j]<<endl;
}
cout<<"Enter Number to search in Array:";
cin>>search_num;
for(int i=0;i<100000;i++){
       if(rand_num_Array[i]==search_num){
           cout<<"Number is at"<<i<<endl;
           break;
       }
}

}

int main ()
{
int Array1[1000];
random_array1(Array1);
  
   int Array2[100000];
   random_array1(Array2);
  
   int n = sizeof(Array1)/sizeof(Array1[0]);
Array_quickSort(Array1, 0, n-1);
cout<<"Sorted array: ";
display_Array(Array1, n);
  

getch();
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.