1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <iostream>
#include <string>
using namespace std;
//Sorts the array of names
void SelectionSort(string [] , int);
//findMin() returns index of minimum value in ary between indexes fst and lst
int findMin(const int ary[], int fst, int lst);
//Searches the sorted array
int binSrch(string ary[], int size, string key);
const int SIZE = 20; // array size
int main()
{
string name;
int results;
char again = 'y';
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", "Rutherford, Greg",
"Javens, Renee", "Harrison, Rose", "Setzer, Cathy",
"Pike, Gordon", "Holland, Beth" };
do {
cout << "Enter name you wish to search for: " ;
cin >> name;
//call selection sort
SelectionSort(names,SIZE);
results = binSrch(names,SIZE,name);
if(results == -1)
cout << name << " does not exist in the array. " << endl;
else
cout << name << " found at index " << results + 1 << " in the array." ;
cout << "Search again? Y/N: ";
cin >> again;
} while (again == 'y' || again == 'Y');
return 0;
}
//Function definitions
int findMin(const string ary[], int fst, int lst)
{
int mndx = fst;
for (int k = fst+1; k < lst; ++k)
if (ary[k] < ary[mndx])
mndx = k;
return mndx;
}
int binSrch(int ary[], int size, int key)
{
int first = 0, // first array element
last = size - 1, // last array element
mid, // midpoint of search
pos = -1; // position of search key
bool found = false; // flag
while (!found && first <= last) {
mid = (first + last) / 2; // calculate midpoint
if (ary[mid] == key) { // key found at mid
found = true;
pos = mid;
} // end-f-thenpart
else if (ary[mid] > key) { // key in lower half
last = mid - 1;
}
else {
first = mid + 1; // key in upper half
}
} // endwhile
return pos;
}
void SelectionSort(string names[], int size)
{
int mndex;
for (int k = 0; k < size - 1; k++) {
mndex = findMin(names, k, size);
if (mndex != k)
swap(names[k], names[mndex]);
} // endfor
}
|
