Question

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 ... Create an array that holds 1000 random integers between 1-1000. Allow the user to enter an integer to search. Create and implement modified Quick sort 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 "Create and implement modified bubble sort algorithm which will sort the array before the Binary Search algorithm is executed.Create and implement Insertion sort algorithm which will sort the array before the Binary Search algorithm is executed.", the insertion sort and the bubble sort.

Answer 1

Editable code

Program

#include<iostream>

#include<cstdlib>

#include <time.h>

#include <ctime>

using namespace std;

int binary_Search(int Arr[], int k, int size) {

     int start = 0;

     int end = size - 1;

     while (start <= end) {

          int mid = (start + end) / 2;

          if (k == Arr[mid]) {

              return mid;

          }

          if (k < Arr[mid]) {

              end = mid - 1;

          }

          else {

              start = mid + 1;

          }

     }

     return -1;

}

void bubble_Sort(int Array[], int size) {

     int t = 0;

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

          for (int j = 1; j < (size - i); j++) {

              if (Array[j - 1] > Array[j]) {

                   //swap the elements!

                   t = Array[j - 1];

                   Array[j - 1] = Array[j];

                   Array[j] = t;

              }

          }

     }

}

int partitioning(int a[], int l, int u)

{

     int v, i, j, temp;

     v = a[l];

     i = l;

     j = u + 1;

     do

     {

          do

              i++;

          while (a[i]<v&&i <= u);

          do

              j--;

          while (v<a[j]);

          if (i<j)

          {

              temp = a[i];

              a[i] = a[j];

              a[j] = temp;

          }

     } while (i<j);

     a[l] = a[j];

     a[j] = v;

     return(j);

}

void quick_sort(int Array[], int l, int u)

{

     int j;

     if (l<u)

     {

          j = partitioning(Array, l, u);

          quick_sort(Array, l, j - 1);

          quick_sort(Array, j + 1, u);

     }

}

void Insertion_sort(int Array[], int size)

{

     int t,i,j;

     for (i = 1; i < size; i++)

     {

          for (j = i; j >= 1; j--)

          {

              if (Array[j] < Array[j - 1])

              {

                   t = Array[j];

                   Array[j] = Array[j - 1];

                   Array[j - 1] = t;

              }

              else

                   break;

          }

     }

}

int main()

{

     clock_t b1, b2,b3;

     double time1, time2;

     srand(time(NULL));

     int array[1000];

     int l = 0;

     cout << "\nQuick Sort";

     while (l < 3)

     {

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

              array[i] = rand() % 1000 + 1;

          }

          int search;

          cout << "\nEnter the search number: ";

          cin >> search;

          quick_sort(array,0,999);

          bubble_Sort(array, 1000);

          int pos = binary_Search(array, search, 1000);

          b1 = clock();

          if (pos != -1) {

              cout << "\nNumber found at position " << pos << endl;

          }

          else {

              cout << "\nNumber not found" << endl;

          }

          time2 = (double)(b1) / CLOCKS_PER_SEC;

          cout << "\nTime taken for search :" << time2;

          l++;

     }

     cout << "\nbubble sort";

     l = 0;

     while (l < 3)

     {

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

              array[i] = rand() % 1000 + 1;

          }

          int search;

          cout << "\nEnter the search number: ";

          cin >> search;

          bubble_Sort(array, 1000);

          int pos = binary_Search(array, search, 1000);

          b2 = clock();

          if (pos != -1) {

              cout << "\nNumber found at position " << pos << endl;

          }

          else {

              cout << "\nNumber not found" << endl;

          }

          time2 = (double)(b2) / CLOCKS_PER_SEC;

          cout << "\nTime taken for search :" << time2;

          l++;

     }

     cout << "\nInsertion sort";

     l = 0;

     while (l < 3)

     {

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

              array[i] = rand() % 1000 + 1;

          }

          int search;

          cout << "\nEnter the search number: ";

          cin >> search;

          Insertion_sort(array, 1000);

          int pos = binary_Search(array, search, 1000);

          b3 = clock();

          if (pos != -1) {

              cout << "\nNumber found at position " << pos << endl;

          }

          else {

              cout << "\nNumber not found" << endl;

          }

          time2 = (double)(b3) / CLOCKS_PER_SEC;

          cout << "\nTime taken for search :" << time2;

          l++;

     }

     cout << endl;

     system("pause");

     return 0;

}