Source of search_sort_demo.cpp


  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: }