f Please use C++ Language. And Note that please donot post the answer already th

Question

f

Please use C++ Language. And Note that please donot post the answer already there Because there is similar answer code but I need with modified Quick sort algorithm . Update your program from where you == 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 previouss code please, the insertion sort and the bubble sort THANK YOU IN ADVANCE.

Explanation / Answer

#include <time.h>

#include <iostream>

using namespace std;

void quickSort(int arr[], int left, int right);

int binarySearch(int arr[], int l, int r, int x);

int main(int argc, const char * argv[])

{

clock_t start_t, end_t, total_t;

start_t=clock();

int ar[100000];

//srand(time(NULL));

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

{

ar[i]=rand()%10000+1;

}

quickSort(ar,0,100000);

int num;

cout<<"Enter a number to be searched for: ";

cin>>num;

int pos=binarySearch(ar,0,100000,num);

if(pos==-1)

cout<<"Element not found";

else

cout<<"Element found at position: "<<pos+1;

end_t=clock();

total_t=(double)(end_t-start_t)/ CLOCKS_PER_SEC;

cout<<" Total time taken: "<<total_t<<endl;

return 0;

}

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--;

}

};

/* recursion */

if (left < j)

quickSort(arr, left, j);

if (i < right)

quickSort(arr, i, right);

}

int binarySearch(int arr[], int l, int r, int x)

{

while (l <= r)

{

int m = l + (r-l)/2;

// Check if x is present at mid

if (arr[m] == x)

return m;

// If x greater, ignore left half

if (arr[m] < x)

l = m + 1;

// If x is smaller, ignore right half

else

r = m - 1;

}

// if we reach here, then element was not present

return -1;

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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