Question

***PLEASE USE C++ LANGUAGE***

Binary Search of Strings

1. Write a version of the selection sort algorithm presented in the unit, which is used to search a list of strings.

2. Write a version of the binary search algorithm presented in the unit, which is used to search a list of strings. (Use the selection sort that you designed above to sort the list of strings.)

3. Create a test program that primes the list with a set of strings, sorts the list, and then prompts the user to enter a search string. Your program should then search the list using your binary search algorithm to determine if the string is in the list. Allow the user to continue to search for strings until they choose to exit the program.

Answer 1

1) Sorting a list of strings using selection sort algorithm

Program

//#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

//Constant globals
const int NUM_NAMES = 20;

//Function protoypes
void selectionSort(string [], int);

int main()
{
string names[NUM_NAMES] = {"Collins, Bill", "Smith, Bart", "Allet, Jim",
"Griffin, Jim", "Stamey, Marty", "Rose, Geri",
"Taylor, Terri", "Johnson, Jill",
"Aliison, Jeff", "Weaver, Jim", "Pore, Bob",
"Rutherford, Greg", "Javens, Renee",
"Harrison, Rose", "Setzer, Cathy",
"Pike, Gordon", "Holland, Beth"};

int i;

//Show array
cout << "The unsorted values are\n";
//showArray(names, NUM_NAMES);
for (i=0;i<NUM_NAMES;i++)
cout<<names[i]<<endl;
  
//Sort array
selectionSort(names, NUM_NAMES);

  
  
return 0;
}

void selectionSort(string array[], int NUM_NAMES)
{
int startScan, minIndex,i;
string minValue;

for(startScan = 0; startScan < (NUM_NAMES -1); startScan++)
{
minIndex = startScan;
minValue = array[startScan];
for(int index = startScan +1; index < NUM_NAMES; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
array[minIndex] = array[startScan];
array[startScan] = minValue;
}
//Display sorted array
cout << "\nThe sorted values are\n";
  
for (i=0;i<NUM_NAMES;i++)
cout<<array[i]<<endl;
}

Output

The unsorted values are Collins, Bill Smith, Bart Allet, Jim Griffin, Jim Stamey, Marty Rose, Geri Taylor, Terri ohnson, Jill Aliison, Jeff Weaver, Jim Pore, Bob Rutherford, Greg Javens, Renee Harrison, Rose Setzer, Cathy Pike, Gordon Holland, Beth

The sorted values are Aliison, Jeff Allet, Jim Collins, Bill Griffin, Jim Harrison, Rose Holland, Beth Javens, Renee ohnson, ill Pike, Gordon Pore, Bob Rose, Geri Rutherford, Greg Setzer, La Smith, Bart Stamey, Marty Taylor, Terri Weaver, Jim

2) Binary Search on Strings

Binary search is performed on sorted arrays. Here we use selection sort to sort input array.

//#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

//Constant globals
const int NUM_NAMES = 20;

//Function protoypes
void selectionSort(string [], int);

int binarySearch(string [], int, string);
int main()
{
string names[NUM_NAMES] = {"Collin", "Smith", "Allet",
"Griffin", "Stamey", "Rose",
"Taylor", "Johnson",
"Aliison", "Weaver", "Pore",
"Rutherford", "Javens",
"Harrison", "Setzer",
"Pike", "Holland"};

int i,results;
string key;

//Show array
cout << "The unsorted values are\n";
//showArray(names, NUM_NAMES);
for (i=0;i<NUM_NAMES;i++)
cout<<names[i]<<endl;
  
//Sort array
selectionSort(names, NUM_NAMES);

cout << "\nPlease enter search string: ";
getline(cin, key);

// Search for name
results = binarySearch(names, NUM_NAMES, key);

// If results contains -1 the name was not found.
if (results == -1)
cout << "\nThat name does not exist in the array.\n";
else
{
// Otherwise results contains the subscript of
// the specified employee ID in the array.
cout << "\nThat name is found at element " << results;
cout << " in the array.\n";
}
  
return 0;
}

void selectionSort(string array[], int NUM_NAMES)
{
int startScan, minIndex,i;
string minValue;

for(startScan = 0; startScan < (NUM_NAMES -1); startScan++)
{
minIndex = startScan;
minValue = array[startScan];
for(int index = startScan +1; index < NUM_NAMES; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
array[minIndex] = array[startScan];
array[startScan] = minValue;
}

  
}
int binarySearch(string names[], int size, string value)
{
int first = 0, // First array element
last = size - 1, // Last array element
middle, // Mid point of search
position = -1; // Position of search value
bool found = false; // Flag

while (!found && first <= last)
{
middle = (first + last) / 2; // Calculate mid point
if (names[middle] == value) // If value is found at mid
{
found = true;
position = middle;
}
else if (names[middle] > value) // If value is in lower half
last = middle - 1;
else
first = middle + 1; // If value is in upper half
}
return position;
}

Output

The unsorted values are Collin Smith Allet Griffir Stamey Rose Taylor Johnson Aliisor Weaver Pore Rutherford Javens Harrison Setzer Pike Holland Please enter search string: Taylor That name is found at element 18 in the array

Program 3

//#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

//Constant globals
const int NUM_NAMES = 20;

//Function protoypes
void selectionSort(string [], int);

int binarySearch(string [], int, string);
int main()
{
string names[NUM_NAMES] = {"Collin", "Smith", "Allet",
"Griffin", "Stamey", "Rose",
"Taylor", "Johnson",
"Aliison", "Weaver", "Pore",
"Rutherford", "Javens",
"Harrison", "Setzer",
"Pike", "Holland"};

int i,results;
string key;
char again;

//Show array
cout << "The unsorted values are\n";
//showArray(names, NUM_NAMES);
for (i=0;i<NUM_NAMES;i++)
cout<<names[i]<<endl;
  
//Sort array
selectionSort(names, NUM_NAMES);
do
{
cout << "\nPlease enter search string: ";
getline(cin, key);

// Search for name
results = binarySearch(names, NUM_NAMES, key);

// If results contains -1 the name was not found.
if (results == -1)
cout << "\nThat name does not exist in the array.\n";
else
{
// Otherwise results contains the subscript of
// the specified employee ID in the array.
cout << "\nThat name is found at element " << results;
cout << " in the array.\n";
}
//Run program again?
cout << "Would you like to search another string? (Y/N): ";
cin >> again;
}while(again == 'y' || again == 'Y');
  
return 0;
}

void selectionSort(string array[], int NUM_NAMES)
{
int startScan, minIndex,i;
string minValue;

for(startScan = 0; startScan < (NUM_NAMES -1); startScan++)
{
minIndex = startScan;
minValue = array[startScan];
for(int index = startScan +1; index < NUM_NAMES; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
array[minIndex] = array[startScan];
array[startScan] = minValue;
}

  
}
int binarySearch(string names[], int size, string value)
{
int first = 0, // First array element
last = size - 1, // Last array element
middle, // Mid point of search
position = -1; // Position of search value
bool found = false; // Flag

while (!found && first <= last)
{
middle = (first + last) / 2; // Calculate mid point
if (names[middle] == value) // If value is found at mid
{
found = true;
position = middle;
}
else if (names[middle] > value) // If value is in lower half
last = middle - 1;
else
first = middle + 1; // If value is in upper half
}
return position;
}