SortAndSearch.cpp – Objectives: Binary Search and Selection sort
You are given a list of 20 names as follows:
{"Collins, Bill", "Smith, Bart", "Michalski, Joe", "Griffin, Jim",
"Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone", "Johnson, Jill",
"Allison, Jeff", "Moreno, Juan", "Wolfe, Bill", "Whitman, Jean",
"Moretti, Bella", "Wu, Hong", "Patel, Renee", "Harrison, Rose",
"Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth"};
Write a program to sort and display the names in alphabet order (use selection sort).
The program prompts the user to enter the name being search (use binary search). The program also makes a correction to upper case the first character of the first and last name (see sample output).
Sample output:
The names in sorted order are:
Allison, Jeff
Collins, Bill
Conroy, Pat
Griffin, Jim
Harrison, Rose
Holland, Beth
Johnson, Jill
Kelly, Sean
Michalski, Joe
Moreno, Juan
Moretti, Bella
Patel, Renee
Rubin, Sarah
Sanchez, Manny
Smith, Bart
Smith, Cathy
Taylor, Tyrone
Whitman, Jean
Wolfe, Bill
Wu, Hong
Type the name to search (Last name, first name):
haRRIson, rOSe
Harrison, Rose was found in the array.
Another name search? (Y/N)y
Type the name to search (Last name, first name):
keLlY, kAY
Kelly, Kay was NOT found in the array.
Another name search? (Y/N)y
// Function prototypes
void displayNames(const string[], int);
Called by main function; passed the array of names and the number of names. Prints the list of names.
void selectionSort(string[], int);
Called by main; passed the array of names and the number of names to sort into alphabetic ascending order.
string upperCaseIt(const string);
Called by main; passed a string being search. Convert the first character of the first and last name of the string passed in to uppercase only.
bool binarySearch(const string[], int, string);
Called by main function; passed the array of strings, the number of strings, and the string being searched for.
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
#include<iostream>
using namespace std;
void displayNames(const string[], int);
void selectionSort(string[], int);
string upperCaseIt(const string);
bool binarySearch(const string[], int, string);
int main(){
string names[20]={"Collins, Bill", "Smith, Bart", "Michalski, Joe", "Griffin, Jim",
"Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone", "Johnson, Jill",
"Allison, Jeff", "Moreno, Juan", "Wolfe, Bill", "Whitman, Jean",
"Moretti, Bella", "Wu, Hong", "Patel, Renee", "Harrison, Rose",
"Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth"};
//sorting names
selectionSort(names,20);
//displaying sorted names
cout<<"The names in sorted order are: "<<endl;
displayNames(names,20);
string name;
char choice='Y';
//looping as long as user wishes
while(choice=='Y'){
//getting the name to be searched
cout<<"Type a name to search (Lastname, first name): "<<endl;
getline(cin,name);
//upper casing name (first letters of first and last name)
name=upperCaseIt(name);
//searching in the array for name
if(binarySearch(names,20,name)){
//found
cout<<name<<" was found in the array"<<endl;
}else{
//not found
cout<<name<<" was not found in the array"<<endl;
}
//asking user if he likes to search again
cout<<"Another name search: (y/n): ";
cin>>choice; //getting choice
choice=toupper(choice); //converting to upper case
//removing newline character from stdin buffer, or it will be
//swallowed by the getline() method in the next loop
fflush(stdin);
}
return 0;
}
//implementation of method to display names
void displayNames(const string names[], int size){
for(int i=0;i<size;i++){
cout<<names[i]<<endl;
}
}
//implementation of method to sort names in alphabetical order
void selectionSort(string names[], int size){
//required variables declaration
string minValue,temp;
int minIndex;
//using selection sort algorithm to sort elements
for(int i=0;i<size-1;i++)
{
minValue=names[i];
minIndex=i;
//finding index of smallest value in unsorted part
for(int j=i+1;j<size;j++)
{
if(minValue>names[j])
{
minValue=names[j];
minIndex=j;
}
}
//swapping elements at indices i and minIndex
temp=names[i];
names[i]=names[minIndex];
names[minIndex]=temp;
}
}
//implementation of method to capitalize first and last names
string upperCaseIt(const string str){
string res="";
bool cap=true; //will capitalize first letter
for(int i=0;i<str.length();i++){
char c=str[i];
if(cap && isalpha(c)){
//current character is a letter and cap is true, so
//converting to upper case
c=toupper(c);
cap=false;
}else if(c==','){
//comma detected, end of first name, so setting cap to true
//to capitalize first letter of last name
cap=true;
}else{
//lower casing character in all other cases
c=tolower(c);
}
//appending to result string
res+=c;
}
return res;
}
//implementation of method to binary search for a value
bool binarySearch(const string names[], int size, string search_term){
//defining required variables, initializing them
int low=0;
int high=size-1;
int mid;
//looping until low is less than or equal to high
while(low<=high){
//finding mid index
mid=(low+high)/2;
if(names[mid]==search_term){
//found
return true;
}else if(names[mid]<search_term){
//searching in second half
low=mid+1;
}else{
//searching in first half
high=mid-1;
}
}
return false; //not found
}
/*OUTPUT*/
The names in sorted order are:
Allison, Jeff
Collins, Bill
Conroy, Pat
Griffin, Jim
Harrison, Rose
Holland, Beth
Johnson, Jill
Kelly, Sean
Michalski, Joe
Moreno, Juan
Moretti, Bella
Patel, Renee
Rubin, Sarah
Sanchez, Manny
Smith, Bart
Smith, Cathy
Taylor, Tyrone
Whitman, Jean
Wolfe, Bill
Wu, Hong
Type a name to search (Lastname, first name):
wHItMaN, jEAN
Whitman, Jean was found in the array
Another name search: (y/n): y
Type a name to search (Lastname, first name):
TayLOR, sWifT
Taylor, Swift was not found in the array
Another name search: (y/n): y
Type a name to search (Lastname, first name):
JOhnson, Jill
Johnson, Jill was found in the array
Another name search: (y/n): n
SortAndSearch.cpp – Objectives: Binary Search and Selection sort You are given a list of 20 names...
Write a main function that declares the names, marks, number of elements as well as the value to be searched for and the index of the returned function calls. Read and display the contents of names and marks. Ask the user for a name and using the linear search return the index to the user. If -1 is returned then the name is not in the file. Otherwise write out the name and mark for that student. Sort the arrays...
Write and test a function in C++ that uses the binary search algorithm to search an array of sorted strings – use a do..while loop to allow user to perform multiple searches w/o terminating the program – see sample output below. Use this name array: string names[SIZE] = { "Collins, Bill", "Smith, Bart", "Allen, Jim", "Griffin, Jim", "Stamey, Marty", "Rose, Geri", "Taylor, Terri", "Johnson, Jill", "Allison, Jeff", "Looney, Joe", "Wolfe, Bill", "James, Jean", "Weaver, Jim", "Pore, Bob",...
This lab is to give you more experience with C++ Searching and Sorting Arrays Given a file with data for names and marks you will read them into two arrays You will then display the data, do a linear search and report if found, sort the data, do a binary search. Be sure to test for found and not found in your main program. Read Data Write a function that reads in data from a file using the prototype below....
C++ I need a program that will read a list of names from a data file and store them in an array. You will then sort the array by last name using a quicksort, and display the results, one name per line.Each line has a first name and a last name.The file has 40 names in it right now, but the array should be able to accommodate up to 50 names.txt***************************************************** Barbara Wright Ian Chesterton Steven Taylor Sara Kingdom Dodo...
C++ with Pseudocode in the beginning This assignment will require you to write a program that will create an array of 10 string objects. The array will be initialized with the strings which contain the person’s name and phone number in one string. The following is an example of test data: “Renee Javens, 678-1223”, “Joe Looney, 586-0097”, “Geri Palmer, 223-8787”, “Lynn Presnell, 887-1212”, “Bill Wolfe, 223-8878”, “Sam Wiggins, 486-0998”, “Bob Kain, 586-8712”, “Tim Haynes, 586-7676”, “John Johnson, 223-9037”, “Jean James,...
The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows: 8. Search Benchmarks Write a program that has at least 20 250 integers stored in an array in ascending order. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that...
In C++ First create the two text file given below. Then complete the main that is given. There are comments to help you. An output is also given You can assume that the file has numbers in it Create this text file: data.txt (remember blank line at end) Mickey 90 Minnie 85 Goofy 70 Pluto 75 Daisy 63 Donald 80 Create this text file: data0.txt (remember blank line at end) PeterPan 18 Wendy 32 Michael 28 John 21 Nana 12...
First create the two text file given below. Then complete the main that is given. There are comments to help you. An output is also given You can assume that the file has numbers in it Create this text file: data.txt (remember blank line at end) Mickey 90 Minnie 85 Goofy 70 Pluto 75 Daisy 63 Donald 80 Create this text file: data0.txt (remember blank line at end) PeterPan 18 Wendy 32 Michael 28 John 21 Nana 12 Main #include...
You are going to implement Treesort algorithm in C++ to sort string data. Here are the steps to complete the homework 1) Use the following class definition for binary search tree nodes. Its constructor is incomplete you should first complete the constructor. class TreeNode t public: string data; / this is the string stored in the node TreeNode left: TreeNode right; TreeNode (string element, TreeNode 1t, TreeNode rt //your code here 2) Write a function that will insert a string...
All those points need to be in the code Project 3 Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort Class River describes river's name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong() that returns true if river is above 30 miles long and returns false otherwise. Class CTRivers describes collection of CT rivers. It has no data, and it provides the...