10. Data struc algorithms c++ Create an array that holds 100000 random integers
ID: 3819024 • Letter: 1
Question
10. Data struc algorithms c++
Create an array that holds 100000 random integers between 1-1000. Allow the user to enter an integer to search. Create and implement Quicksort algorithm which will sort the array before the Binary Search algorithm is executed. Create and implement a Binary Search Algorithm. If the number exists in the array and output the position. If the search key does not exist in the Array simple output value not found. Use the clock(); method to time the execution of the search and sort Execute the program 3 times. Twice running the modified Quick sort as the sorting algorithm. Describe your results in relation to Assignment 7, the insertion sort and the bubble sort Attach Photos of Source Code and OutputExplanation / Answer
/*
C++ program that prompts user to enter a search value
and search the element in the array. The print the position
of element if found and time taken to search.
*/
//binarysearch.cpp
//header files
#include<iostream>
#include<time.h>
using namespace std;
//function prototypes
void initialize(int arr[],int size)
void quickSort(int arr[], int left, int right) ;
void binarySearch(int arr[], int first, int last,int search);
int main()
{
srand(time_t(0));
int size=100000;
int arr[100000];
int search;
//initialize the array
initialize(arr,size);
//calling quicksort
quickSort(arr,0,size-1);
cout<<"Please enter a value to search";
cin>>search;
time_t start,end;
time(&start);
//calling binarySearch method
binarySearch(arr,0,size-1,search);
time(&end);
//calculates the time difference in milliseconds
double milliSeconds =difftime(end,start)/CLOCKS_PER_SEC;
cout<<"Milliseconds : "<<milliSeconds<<endl;
system("pause");
return 0;
}
//Method that intializes the array in a range of 1-1000
void initialize(int arr[],int size)
{
for (int index=0;index<size;index++)
{
arr[index]=rand()%1000+1;
}
}
//The method binary search that print position of element to be searched
//if found otherwise print element not found
void binarySearch(int arr[], int first, int last,int search)
{
int middle = (first+last-1)/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.";
}
}
//Sorting array using quiksort algorithm
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
sample output:
Please enter a value to search999
999 found at location 99854
Milliseconds : 0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.