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