1: //search_sort_demo.cpp
2: //Demonstrates searching and sorting in arrays,
3: //as well as random generation of array elements.
5: #include <iostream>
6: #include <cstdlib> //For access to functions rand and srand
7: #include <ctime> //For access to function clock
8: using namespace std;
10: #include "utilities.h"
11: using Scobey::Pause;
12: using Scobey::Menu;
13: using Scobey::TextItems;
16: const int MAX_SIZE = 20;
17: /**<
18: The maximum size of the array to be searched or sorted.
19: */
21: typedef int ComponentType;
22: /**<
23: A name for the type of the components to be stored in the array.
24: */
26: void GenerateRandomValues
27: (
28: ComponentType a[], //out
29: int& currentSize //out
30: );
31: /**<
32: Generate an array of random integer values.
33: @return void
34: @param a The array of integer values.
35: @param currentSize The size of the array <em>a</em>.
36: @pre None
37: @post <em>currentSize</em> has been entered by the user, and
38: <em>a</em> contains <em>currentSize</em> randomly chosen integer
39: values.
40: */
42: void DisplayArrayValues
43: (
44: const ComponentType a[], //in
45: int currentSize //in
46: );
47: /**<
48: Display all values in an array of values.
49: @return void
50: @param a The array whose values are to be displayed.
51: @param currentSize The size of the array <em>a</em>.
52: @pre <em>a</em> has been initialized.
53: @post The values of <em>a</em> have been displayed, with two blank
54: spaces separating each two values.
55: */
57: void SortViaSelection
58: (
59: ComponentType a[], //inout
60: int currentSize //in
61: );
62: /**<
63: Sort an array of valuew into ascending order using Selection Sort.
64: @return void
65: @param a The array of values to be sorted.
66: @param currentSize The size of the array <em>a</em>.
67: @pre <em>a</em> has been initialized.
68: @post The values in <em>a</em> have been sorted into ascending order.
69: */
71: void HandleSearches
72: (
73: const ComponentType a[], //in
74: int currentSize //in
75: );
76: /**<
77: Get a target value, search range and choice of search method from the
78: user, perform the search, and report the results.
79: @return void
80: @param a The array of values to be searched.
81: @param currentSize The size of the array <em>a</em> to be searched.
82: @pre <em>a</em> has been initialized.
83: @post A search for a "target value" in <em>a</em> has been performed.
84: */
86: void SearchLinear
87: (
88: const ComponentType a[], //in
89: ComponentType target, //in
90: int first, //in
91: int last, //in
92: int& index, //out
93: bool& found //out
94: );
95: /**<
96: Search for a value in an array of values using linear search.
97: @return void
98: @param a The array of values to be searched.
99: @param target The value for which to search.
100: @param first The position (not the index) of the start of the search range.
101: @param last The position (not the index) of the end of the search range.
102: @param found The indicator of success or failure of the search.
103: @pre
104: - <em>a</em>, <em>target</em>, <em>first</em> and <em>last</em>
105: have been initialized
106: - <em>1 <= first <= last <= MAX_SIZE</em>.
107: @post Either
108: <br><em>found == true</em> and <em>a[index] == target</em>, or
109: <br><em>found == false</em> and <em>index == last</em>.
110: */
112: void SearchBinary
113: (
114: const ComponentType a[], //in
115: ComponentType target, //in
116: int first, //in
117: int last, //in
118: int& index, //out
119: bool& found //out
120: );
121: /**<
122: Search for a value in an array of values using binary search.
123: @return void
124: @param a The array of values to be searched.
125: @param target The value for which to search.
126: @param first The position (not the index) of the start of the search range.
127: @param last The position (not the index) of the end of the search range.
128: @param found The indicator of success or failure of the search.
129: @pre <em>a</em>, <em>target</em>, <em>first</em> and <em>last</em>
130: have been initialized, and <em>1 <= first <= last <= MAX_SIZE</em>.
131: The values in <em>a</em> are sorted in ascending order.
132: @post Either
133: <br><em>found == true</em> and <em>a[index] == target</em>, or
134: <br><em>found == false</em> and <em>index</em> is undefined.
135: */
137: int main()
138: {
139: Menu m("Main Menu");
140: m.addOption("Quit");
141: m.addOption("Get information");
142: m.addOption("Generate a new array");
143: m.addOption("Display the array");
144: m.addOption("Sort the array in ascending order");
145: m.addOption("Search the array for a target value");
147: TextItems text("search_sort_demo.txt");
149: ComponentType a[MAX_SIZE];
150: int currentSize = 0;
151: int menuChoice;
153: do
154: {
155: m.display();
156: menuChoice = m.getChoice();
157: switch (menuChoice)
158: {
159: case -1:
160: case 1:
161: break;
162: case 2:
163: text.displayItem("Program Description");
164: break;
165: case 3:
166: GenerateRandomValues(a, currentSize);
167: break;
168: case 4:
169: DisplayArrayValues(a, currentSize);
170: break;
171: case 5:
172: SortViaSelection(a, currentSize);
173: break;
174: case 6:
175: HandleSearches(a, currentSize);
176: break;
177: }
178: }
179: while ((menuChoice != 1) && (menuChoice != -1));
180: }
182: //******************************************************************
183: void GenerateRandomValues
184: (
185: ComponentType a[], //out
186: int& currentSize //out
187: )
188: {
189: srand(clock()); //Establish a random "seed" for calling rand
191: cout << "\nHow many array elements (no more than "
192: << MAX_SIZE << ") would you like? ";
193: cin >> currentSize; cin.ignore(80, '\n'); cout << endl;
195: cout << "What range would you like your values to lie in?"
196: "\nEnter first and last values for the range: ";
197: ComponentType first, last;
198: cin >> first >> last; cin.ignore(80, '\n'); cout << endl;
200: //Get currentSize random values in range first..last.
201: for (int i = 0; i < currentSize; i++)
202: a[i] = first + rand() % (last - first + 1);
203: }
205: //******************************************************************
206: void DisplayArrayValues
207: (
208: const ComponentType a[], //in
209: int currentSize //in
210: )
211: {
212: cout << endl;
213: for (int i = 0; i < currentSize; i++)
214: cout << a[i] << " ";
215: cout << endl << endl;
216: Pause();
217: }
219: //******************************************************************
220: void SortViaSelection
221: (
222: ComponentType a[], //inout
223: int currentSize //in
224: )
225: {
226: ComponentType temp;
227: int minIndex;
229: for (int pass = 0; pass < currentSize - 1; pass++)
230: {
231: minIndex = pass;
232: for (int position = pass + 1; position < currentSize; position++)
233: if (a[position] < a[minIndex]) minIndex = position;
235: temp = a[minIndex];
236: a[minIndex] = a[pass];
237: a[pass] = temp;
238: }
239: }
241: //******************************************************************
242: void HandleSearches
243: (
244: const ComponentType a[], //in
245: int currentSize //in
246: )
247: {
248: cout << endl;
249: cout << "What value would you like to search for? ";
250: ComponentType target;
251: cin >> target; cin.ignore(80, '\n'); cout << endl;
253: cout << "Between what two positions would you like to search? ";
254: int first, last;
255: cin >> first >> last; cin.ignore(80, '\n'); cout << endl;
257: cout << "\nYou have a choice of linear or binary search."
258: "\nBut, you can only use binary search on a sorted list."
259: "\nWhich would you like to use? (L/B) ";
260: char response;
261: cin >> response; cin.ignore(80, '\n'); cout << endl;
263: bool found;
264: int index;
265: switch (response)
266: {
267: case 'L':
268: case 'l':
269: SearchLinear(a, target, first, last, index, found);
270: break;
272: case 'B':
273: case 'b':
274: SearchBinary(a, target, first, last, index, found);
275: break;
276: }
278: cout << endl << target;
279: if (found)
280: cout << " located at position " << index + 1 << "." << endl;
281: else
282: cout << " not found." << endl;
283: cout << endl;
285: Pause();
286: }
288: //******************************************************************
289: void SearchLinear
290: (
291: const ComponentType a[], //in
292: ComponentType target, //in
293: int first, //in
294: int last, //in
295: int& index, //out
296: bool& found //out
297: )
298: {
299: index = first - 1;
300: while ((index <= last - 1) && (target != a[index])) ++index;
301: found = (index < last);
302: }
304: //******************************************************************
305: void SearchBinary
306: (
307: const ComponentType a[], //in
308: ComponentType target, //in
309: int first, //in
310: int last, //in
311: int& index, //out
312: bool& found //out
313: )
314: {
315: int low = first;
316: int high = last;
317: int middle;
318: found = false;
319: while (high >= low && !found)
320: {
321: middle = (low + high) / 2;
322: if (target < a[middle])
323: high = middle - 1;
324: else if (target > a[middle])
325: low = middle + 1;
326: else
327: found = true;
328: }
329: index = middle;
330: }