Update your program

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 Output

Code:

#include #include #include using namespace std;

void fillArray(int arr[], int n) { for(int i = 0; i < n ; i++) { arr[i] = (rand() % 1000) + 1; } }

// A utility function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }

/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ int 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); }

/* The main function that implements QuickSort arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ void quickSort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high);

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

// A recursive binary search function. It returns location of x in // given array arr[l..r] is present, otherwise -1 int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l)/2;

// If the element is present at the middle itself if (arr[mid] == x) return mid;

// If element is smaller than mid, then it can only be present // in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right subarray return binarySearch(arr, mid+1, r, x); }

// We reach here when element is not present in array return -1; }

int main() { int n = 1000; int arr[n]; fillArray(arr, n);

int num;

for(int i = 0; i < 2; i++) { cout << "Enter a number between 1-1000 to search: "; cin >> num; clock_t t; t = clock(); quickSort(arr, 0, n); cout << "Sort took " << ((float)(clock() - t)) << endl;; t = clock(); int position = binarySearch(arr, 0, n, num); cout << "Search took " << ((float)(clock() - t)) << endl; if (position == -1) { cout << "Value not found "; } else { cout << "Number exist at " << position << " position in array "; } } }