Update your program Create an array that holds 100000 random integers between 1-

Question

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 <iostream>
#include <stdlib.h>
#include <time.h>
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 ";
}
}
}

Explanation / Answer

Answer:-

QuickSort :-
#include <stdio.h>

void swap ( int* a, int* b )
{
   int t = *a;
   *a = *b;
   *b = t;
}

int partition (int arr[], int l, int h)
{
   int x = arr[h];
   int i = (l - 1);

   for (int j = l; j <= h- 1; j++)
   {
       if (arr[j] <= x)
       {
           i++;
           swap (&arr[i], &arr[j]);
       }
   }
   swap (&arr[i + 1], &arr[h]);
   return (i + 1);
}

void quickSortIterative (int arr[], int l, int h)
{
   // Create an auxiliary stack
   int stack[ h - l + 1 ];

   // initialize top of stack
   int top = -1;

   // push initial values of l and h to stack
   stack[ ++top ] = l;
   stack[ ++top ] = h;

   // Keep popping from stack while is not empty
   while ( top >= 0 )
   {
       // Pop h and l
       h = stack[ top-- ];
       l = stack[ top-- ];

       // Set pivot element at its correct position
       // in sorted array
       int p = partition( arr, l, h );

       // If there are elements on left side of pivot,
       // then push left side to stack
       if ( p-1 > l )
       {
           stack[ ++top ] = l;
           stack[ ++top ] = p - 1;
       }

       // If there are elements on right side of pivot,
       // then push right side to stack
       if ( p+1 < h )
       {
           stack[ ++top ] = p + 1;
           stack[ ++top ] = h;
       }
   }
}

// A utility function to print contents of arr
void printArr( int arr[], int n )
{
   int i;
   for ( i = 0; i < n; ++i )
       printf( "%d ", arr[i] );
}

// Driver program to test above functions
int main()
{
   int arr[] = {4, 3, 5, 2, 1, 3, 2, 3};
   int n = sizeof( arr ) / sizeof( *arr );
   quickSortIterative( arr, 0, n - 1 );
   printArr( arr, n );
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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