Chapter 8

Question 1

linear search algorithm(array)

Answer 1

loop to sequentially step through an array, starting with the first element. It compares each element with the value being searched for, and stops when either the value is found or the end of the array is encountered.

Question 2

write the code for a linear search algorithm

Answer 2

int linearSearch (const int arr[], int size, int value) {
  int index = 0;       
// Used as a subscript to search the array
  int position = −1;   // To record the position of the search value
  bool found = false;  // Flag to indicate if the value was found
  while (index < size && !found)  {
     if (arr[index] == value) {
        found = true;         
        position = index;     
     }
     index++;                  
  }
  return position;               
}

Question 3

binary search algorithm(array)

Answer 3

searches a sorted array. testing the middle element. If the middle element is not a match it is either greater or less than the desired value. This eliminates half of the elements. The search continues at the next middle element and so on.

Question 4

write a binary search algorithm

Answer 4

int binarySearch (const int arr[], int size, int value) {
int first = 0, // first array element
last = size -1, // last array element
middle, // midpoint of search
int position = −1; // position of the search value
bool found = false; // Flag
while (first <= last && !found) {
middle = (first + last) / 2; // calculate midpoint
if (arr[middle] == value) { // if value is found at mid point
found = true;
position = middle; }
else if (array[middle] > value) { // if value is in lower half
last = middle - 1; }
else {
first = middle + 1; // if value is in upper half }
return position;
}

Question 5

bubble sort

Answer 5

void bubbleSort(int array[], int size) {
  int maxElement; // hold the subscript of the last element to be compared to neighbor
  int index; 

  for (maxElement = size -1; maxElement > 0; maxElement--) {
	// loop will iterate once for each element in array
	//
	  for (index = 0; index < maxElement; index++) {
		  if (array[index] > array[index + 1]) {
			  swap(array[index], array[index+1]);
			}
		}

  }
}

Question 6

selection sort

Answer 6

void selectionSort(int array[], int size) {
   int minIndex, minValue;
	 
	 for (int start = 0; start < (size - 1); start++) {
	    minIndex = start;
		  minValue = array[start];
   
	    for (int index = start + 1; index < size; index++) {
         if (array[index] < minValue) {
		        minValue = array[index];
			      minIndex = index; }
	    }
			
	    swap(array[minIndex], array[start]);
   }
	 
}

Question 7

swap function (swap the value of two variables)

Answer 7

void swap(int &a, int &b){
int temp = a;
a = b;
b = temp; }