Question

1. Write a program that meets the following criteria:
   1. Define a function that implements the selection sort algorithm to sort an integer array.
   2. Define a function that implements the binary search algorithm to search an array for a given integer. The function must return the location of the integer if it is found or a -1 if it is not found.
   3. The main function in your program must declare an integer array initialized with 10 unsorted values. The main function must use the selection sort function to sort the array. Next, the main function must demonstrate at least one call to the binary search function where the function finds a value in the array and one call where it does not.
   4. The definition of the main function must appear above the definition of the selection sort and binary search functions in your code.

I am in programming II with C++.

Answer 1

CODE

#include <iostream>

using namespace std;

void bubbleSort(int [], int);

void swap(int *, int *);

int binarySearch(int [], int, int, int);

int main() {

int arr[] = {64, 34, 25, 12, 22, 11, 90, 17, 9, 88};

int n = sizeof(arr)/sizeof(arr[0]);

bubbleSort(arr, n);

int val = 12;

int pos = binarySearch(arr, 0, n-1, val);

if (pos != -1) {

cout << val << " found at position " << pos << endl;

} else {

cout << "Element not found!!" << endl;

}

val = 20;

pos = binarySearch(arr, 0, n-1, val);

if (pos != -1) {

cout << val << " found at position " << pos << endl;

} else {

cout << "Element not found!!" << endl;

}

return 0;

}

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

// A function to implement bubble sort

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

// Last i elements are already in place

for (j = 0; j < n-i-1; j++)

if (arr[j] > arr[j+1])

swap(&arr[j], &arr[j+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;

}

OUTPUT

12 found at position 2
Element not found!!