// please use c++ and read instructions carefully 1) Write a program that reads
ID: 3878480 • Letter: #
Question
// please use c++ and read instructions carefully 1) Write a program that reads 20 names from a file called names.dat and stores them in two different arrays (eg names1, names2). 2) Print the unsorted array of names 3) Now write a function that takes names1 and sorts the names using selection sort. Count how many comparisons are needed to sort the 20 names. Print the sorted array contents and the number of comparisons needed. 4) Next, write a function to sort names2 with the bubblesort routine. Count how many comparisons are needed to sort the array with bubblesort. Print the sorted array and the number of comparisons needed 5) Now write a function that asks the user to enter in a name (one that is stored in the names1 and names files 6) Use the binary search method to look up the name in the sorted array. Display how many comparisons were needed to find the name using the binary search method.
Explanation / Answer
Given below is the code for the question.
Please do rate the answer if it was helpful. Thank you
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
void display(string message, string names[], int n);
int selectionSort(string names[], int n); //returns no. of comparisons
int bubbleSort(string names[], int n); //returns no. of comparisons
int binarySearch(string names[], int n, string search, int &comparisons); //no. of comparisons returned in reference variable
int main()
{
char filename[20];
cout << "Enter input filename: ";
cin >> filename;
ifstream infile(filename);
if(!infile.is_open())
{
cout << "Error opening input file " << filename << endl;
return 1;
}
//load the names from file
string names1[50], names2[50];
int n = 0;
while(getline(infile, names1[n]))
{
names2[n] = names1[n];
n++;
}
infile.close();
display("Unsorted names loaded from file", names1, n);
int comparisons;
comparisons = selectionSort(names1, n);
display("Names sorted using selection sort", names1, n);
cout << "No. of comparsions using selection sort: " << comparisons << endl << endl;
comparisons = bubbleSort(names2, n);
display("Names sorted using bubble sort", names2, n);
cout << "No. of comparsions using bubble sort: " << comparisons << endl << endl;
cin.ignore();
string search = "";
int index;
while(search != "quit")
{
cout << "Enter a name to search(type quit to stop): ";
getline(cin, search);
if(search == "quit")
break;
index = binarySearch(names1, n, search, comparisons);
if(index == -1)
cout << search << " NOT found. No. of comparisons is " << comparisons << endl << endl;
else
cout << search << " found at index " << index << ". No. of comparisons is " << comparisons << endl << endl;
}
}
void display(string message, string names[], int n)
{
cout << message << endl;
cout << left << setw (7) << "Index" << setw(20) << "Word" << endl;
for(int i = 0; i < n; i++)
cout << left << setw (7) << i << setw(20) << names[i] << endl;
cout << endl << endl;
}
int selectionSort(string names[], int n)
{
int minIdx;
string temp;
int comparisons = 0;
for(int i = 0; i < n; i++)
{
minIdx = i;
for(int j = i+1; j < n; j++)
{
if(names[j] < names[minIdx])
{
minIdx = j;
comparisons++;
}
}
if(i != minIdx) //swap?
{
temp = names[i];
names[i] = names[minIdx];
names[minIdx] = temp;
}
}
return comparisons;
}
int bubbleSort(string names[], int n)
{
int comparisons = 0;
for(int i = 0; i < n - 1; i++)
{
for(int j = 0; j < n - i - 1; j++)
{
if(names[j] > names[j+1]) //compare 2 consecutive locations and swap if needed
{
string temp = names[j];
names[j] = names[j+1];
names[j+1] = temp;
comparisons++;
}
}
}
return comparisons;
}
int binarySearch(string names[], int n, string search, int &comparisons)
{
int low = 0, high = n-1;
int mid;
comparisons = 0;
while(low <= high)
{
comparisons++;
mid = (low + high)/2;
if(names[mid] == search)
return mid;
else if(search < names[mid])
high = mid -1;
else
low = mid + 1;
}
return -1;//when not found
}
input file: names.dat
=====================
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
Rutherford Greg
Javens Renee
Harrison Rose
Setzer Cathy
Pike Gordon
Holland Beth
output
=======
Enter input filename: names.dat
Unsorted names loaded from file
Index Word
0 Collins Bill
1 Smith Bart
2 Allen Jim
3 Griffin Jim
4 Stamey Marty
5 Rose Geri
6 Taylor Terri
7 Johnson Jill
8 Allison Jeff
9 Looney Joe
10 Wolfe Bill
11 James Jean
12 Weaver Jim
13 Pore Bob
14 Rutherford Greg
15 Javens Renee
16 Harrison Rose
17 Setzer Cathy
18 Pike Gordon
19 Holland Beth
Names sorted using selection sort
Index Word
0 Allen Jim
1 Allison Jeff
2 Collins Bill
3 Griffin Jim
4 Harrison Rose
5 Holland Beth
6 James Jean
7 Javens Renee
8 Johnson Jill
9 Looney Joe
10 Pike Gordon
11 Pore Bob
12 Rose Geri
13 Rutherford Greg
14 Setzer Cathy
15 Smith Bart
16 Stamey Marty
17 Taylor Terri
18 Weaver Jim
19 Wolfe Bill
No. of comparsions using selection sort: 26
Names sorted using bubble sort
Index Word
0 Allen Jim
1 Allison Jeff
2 Collins Bill
3 Griffin Jim
4 Harrison Rose
5 Holland Beth
6 James Jean
7 Javens Renee
8 Johnson Jill
9 Looney Joe
10 Pike Gordon
11 Pore Bob
12 Rose Geri
13 Rutherford Greg
14 Setzer Cathy
15 Smith Bart
16 Stamey Marty
17 Taylor Terri
18 Weaver Jim
19 Wolfe Bill
No. of comparsions using bubble sort: 89
Enter a name to search(type quit to stop): James Jean
James Jean found at index 6. No. of comparisons is 3
Enter a name to search(type quit to stop): Wolfe Bill
Wolfe Bill found at index 19. No. of comparisons is 5
Enter a name to search(type quit to stop): Allison Jeff
Allison Jeff found at index 1. No. of comparisons is 3
Enter a name to search(type quit to stop): Jeff
Jeff NOT found. No. of comparisons is 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.