Help with my program. Here is my program that I wrote. It works it creates an ar

Question

Help with my program.

Here is my program that I wrote. It works it creates an array of test data, another array of search keys, and then runs the search algorithms. The linear search already contains a statement which counts its comparisons. I need to modify the sortedSearch and binarySearch functions so that they also track these metrics. I need to use the global variables that are already declared.

#include <iostream>

#include <ctime>

using namespace std;

// Global variables (JUST THIS ONCE)

long linearCount = 0;

long sortedCount = 0;

long binaryCount = 0;

void display(int *list, int size)

{

for (int i = 0; i < size; i++)

cout << list[i] << " ";

cout << endl;

}

void bubbleSort(int *list, int size)

{

for (int numIterations = 0; numIterations < size; numIterations++)

{

for (int i = 0; i < size - 1; i++)

{

if (list[i] > list[i + 1])

{

int temp = list[i + 1];

list[i + 1] = list[i];

list[i] = temp;

}

}

//cout << " AFTER ITERATION " << numIterations << endl;

//display(list, size);

}

}

int linearSearch(int *list, int size, int key)

{

int index = -1;

for (int i = 0; i < size; i++)

{

linearCount++;

if (list[i] == key)

{

index = i;

break;

}

}

return index;

}

int sortedSearch(int *list, int size, int key)

{

int i = 0;

while (i < size && list[i] <= key)

{

if (list[i] == key)

return i;

i++;

}

return -1;

}

int binarySearch(int *list, int size, int key)

{

int begin = 0;

int end = size - 1;

while (begin <= end)

{

int middle = (begin + end) / 2;

if (list[middle] == key)

return middle;

else if (key < list[middle])

end = middle - 1;

else

begin = middle + 1;

}

return -1;

}

void main()

{

const int NUM_SEARCHES = 20;

const int SIZE = 1000;

int list[SIZE];

int testValues[NUM_SEARCHES];

srand(time(0));

for (int i = 0; i < SIZE; i++)

list[i] = rand() % (SIZE*5);

for (int i = 0; i < NUM_SEARCHES; i++)

testValues[i] = rand() % (SIZE * 5);

cout << " DATA SET:" << endl;

display(list, SIZE);

cout << " SEARCH KEYS:" << endl;

display(testValues, NUM_SEARCHES);

cout << " LINEAR SEARCH TEST" << endl;

for (int i = 0; i < NUM_SEARCHES; i++)

{

int index = linearSearch(list, SIZE, testValues[i]);

if (index == -1)

cout << "Did not find " << testValues[i] << endl;

else

cout << "Found " << testValues[i] << " at index " << index << endl;

}

bubbleSort(list, SIZE);

cout << " SORTED SEARCH TEST" << endl;

for (int i = 0; i < NUM_SEARCHES; i++)

{

int index = sortedSearch(list, SIZE, testValues[i]);

if (index == -1)

cout << "Did not find " << testValues[i] << endl;

else

cout << "Found " << testValues[i] << " at index " << index << endl;

}

cout << " BINARY SEARCH TEST" << endl;

for (int i = 0; i < NUM_SEARCHES; i++)

{

int index = binarySearch(list, SIZE, testValues[i]);

if (index == -1)

cout << "Did not find " << testValues[i] << endl;

else

cout << "Found " << testValues[i] << " at index " << index << endl;

}

cout << " SUMMARY:" << endl;

cout << "Linear Search Comparisons: " << linearCount << endl;

cout << "Sorted Search Comparisons: " << sortedCount << endl;

cout << "Binary Search Comparisons: " << binaryCount << endl;

system("pause");

}

Explanation / Answer

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

// Global variables to count how many comparisons required
long linearCount = 0;
long sortedCount = 0;
long binaryCount = 0;

// Function to display the data set
void display(int *list, int size)
{
// Loops till end of the data set
for (int i = 0; i < size; i++)
// Displays each element data
cout << list[i] << " ";
cout << endl;
}// End of function

// Function to sort the list using bubble sort
void bubbleSort(int *list, int size)
{
// Loops till end of the list
for (int numIterations = 0; numIterations < size; numIterations++)
{
// Loops till size of the list minus one times
for (int i = 0; i < size - 1; i++)
{
// Checks if the i index position value is greater than the next index position of i value
if (list[i] > list[i + 1])
{
// Swapping process
int temp = list[i + 1];
list[i + 1] = list[i];
list[i] = temp;
}// End of if condition
}// End of inner for loop
//cout << " AFTER ITERATION " << numIterations << endl;
//display(list, size);
}// End of outer for loop
}// End of function

// Function to search a key in the list using linear search
// Returns found index position if found otherwise returns -1
int linearSearch(int *list, int size, int key)
{
// Initially found index position is -1 for not found
int index = -1;
// Loops till end of the list
for (int i = 0; i < size; i++)
{
// Increase the counter by one
linearCount++;
// Checks if the current index position value is equals to key value
if (list[i] == key)
{
// Updates the index by i value
index = i;
// Comes out of the loop
break;
}// End of if condition
}// End of for loop
// Returns the index
return index;
}// End of function

// Function to search a key in the list using sorted search
// Returns found index position if found otherwise returns -1
int sortedSearch(int *list, int size, int key)
{
int i = 0;
// Loops till if it reaches end of the list and current index position value is less than or equals to key value
while (i < size && list[i] <= key)
{
// Increase the counter by one
sortedCount++;
// Checks if the current index position value is equals to key value
if (list[i] == key)
// Returns the found index position as i value
return i;
// Increase the loop variable by one
i++;
}// End of while loop
// Returns -1 for not found
return -1;
}// End of function

// Function to search a key in the list using binary search
// Returns found index position if found otherwise returns -1
int binarySearch(int *list, int size, int key)
{
// Initializes the beginning index position of the list to zero
int begin = 0;
// Initializes the last index position of the list to size minus one
int end = size - 1;

// Loops till beginning is less than or equals to end
while (begin <= end)
{
// Increase the counter by one
binaryCount++;
// Calculates the middle index position
int middle = (begin + end) / 2;

// Checks if the middle index position value is equals to key value
if (list[middle] == key)
// Returns the found index position as middle value
return middle;
// Otherwise checks if key value is less than the middle index position value of the list
else if (key < list[middle])
// Update the end index position by middle minus one
end = middle - 1;
// Otherwise the key value is greater than the middle index position value of the list
else
// Update the beginning index position by middle plus one
begin = middle + 1;
}// End of while loop
// Returns -1 for not found
return -1;
}// End of while loop

// main function definition
int main()
{
// Defines a constant for number of searches to 20
const int NUM_SEARCHES = 20;
// Defines a constant for list size to 1000
const int SIZE = 1000;
// Declares an array of size 1000
int list[SIZE];
// Declares an array of size 20 to store search numbers
int testValues[NUM_SEARCHES];
srand(time(0));

// Loops till end of the list size
for (int i = 0; i < SIZE; i++)
// Generates random number and stores it in array
list[i] = rand() % (SIZE * 5);

// Loops till end of the searched array size
for (int i = 0; i < NUM_SEARCHES; i++)
// Generates random number and stores it in array
testValues[i] = rand() % (SIZE * 5);

// Calls the function to display the list
cout << " DATA SET:" << endl;
display(list, SIZE);

// Calls the function to display the search array
cout << " SEARCH KEYS:" << endl;
display(testValues, NUM_SEARCHES);

cout << " LINEAR SEARCH TEST" << endl;
// Loops till end of the search array size
for (int i = 0; i < NUM_SEARCHES; i++)
{
// Calls the function to perform linear search and store the found index status
int index = linearSearch(list, SIZE, testValues[i]);
// Checks if found index position is -1 then display message key not found with search key value
if (index == -1)
cout << "Did not find " << testValues[i] << endl;
// Otherwise, display the search key with found index position
else
cout << "Found " << testValues[i] << " at index " << index << endl;
}// End of for loop

// Calls the function to perform bubble sort
bubbleSort(list, SIZE);
cout << " SORTED SEARCH TEST" << endl;
// Loops till end of the search array size
for (int i = 0; i < NUM_SEARCHES; i++)
{
// Calls the function to perform sorted search and store the found index status
int index = sortedSearch(list, SIZE, testValues[i]);
// Checks if found index position is -1 then display message key not found with search key value
if (index == -1)
cout << "Did not find " << testValues[i] << endl;
// Otherwise, display the search key with found index position
else
cout << "Found " << testValues[i] << " at index " << index << endl;
}// End of for loop

cout << " BINARY SEARCH TEST" << endl;
// Loops till end of the search array size
for (int i = 0; i < NUM_SEARCHES; i++)
{
// Calls the function to perform binary search and store the found index status
int index = binarySearch(list, SIZE, testValues[i]);
// Checks if found index position is -1 then display message key not found with search key value
if (index == -1)
cout << "Did not find " << testValues[i] << endl;
// Otherwise, display the search key with found index position
else
cout << "Found " << testValues[i] << " at index " << index << endl;
}// End of for loop

cout << " SUMMARY:" << endl;
// Displays counter value of each search
cout << "Linear Search Comparisons: " << linearCount << endl;
cout << "Sorted Search Comparisons: " << sortedCount << endl;
cout << "Binary Search Comparisons: " << binaryCount << endl;
system("pause");
return 0;
}// End of main function

Sample Output:

DATA SET:
2920 2152 3599 4582 1112 2500 144 2786 4486 4617 439 1067 3821 4042 2584 592 3906 313 1208 924 488 3032 4344 2015 4087 2141 1901 978 3069 1958 4061 2377 3111 4864 2882 1733 1249 279 1547 4275 2717 225 4588 4263 1897 1795 3538 773 2556 937 2876 865 3586 3567 1399 1397 4630 1766 608 2371 2631 4780 599 124 2350 3946 4578 1465 271 1084 455 1800 1558 1148 4751 1481 3500 4960 1351 3944 2778 926 3761 3454 1069 3877 4275 1276 3731 2805 2197 3199 3581 4378 1768 2402 1477 2389 1830 3696 4913 4508 4053 3698 353 2011 160 2592 510 554 4239 259 3379 888 2998 2866 1457 3825 2108 739 4549 45 4972 4509 1501 1657 2513 3195 1195 649 302 3468 3248 2918 2355 2576 541 524 959 1518 2214 600 2178 3604 888 592 4474 2238 3445 3819 3562 3147 2965 2963 1453 1932 4383 3600 1145 759 4929 2807 3801 3171 1292 2530 1515 2548 747 170 1508 1137 3077 1506 1817 1604 1161 4502 759 986 2602 347 1205 2828 3651 737 608 1221 2628 2199 4343 2085 2662 942 1425 317 1932 1800 4444 924 1690 282 3151 610 1666 4152 4330 2851 541 1240 868 4182 1367 4906 4901 614 2838 3934 3390 1552 3508 526 3317 670 2099 2990 3181 2540 464 3569 190 1522 1811 430 3680 2521 4494 3267 1494 209 1396 1360 1337 2553 661 2839 4578 1073 4479 50 4429 613 2238 2198 2642 978 3039 4887 1061 4823 1825 149 3400 2428 3342 2109 2336 1805 2177 4122 2917 2509 2119 2877 1846 877 2203 35 1301 276 1317 1814 2574 587 907 4143 2494 1209 235 3962 2969 37 1127 1002 3252 2698 74 439 2573 3520 506 301 3808 624 4894 199 4595 1816 3962 156 1196 264 4889 577 3658 4404 706 4367 2577 1603 534 1702 4329 1175 353 2298 2825 126 3519 773 4832 2304 4913 3701 2205 858 160 2431 2696 3691 4705 716 3225 2349 2218 2387 4959 1182 4076 3120 1499 2832 2969 2060 2014 3581 1128 1820 1959 4007 3982 390 3234 1222 3240 3993 1214 3787 2150 604 1246 1638 3914 4235 1946 1043 4657 2989 206 162 4257 2265 164 375 1436 3682 4342 487 3019 2897 2166 2372 2791 730 3881 2922 2964 4161 2305 1491 584 2679 4555 1448 3474 4847 4217 666 1278 54 2344 2400 200 1443 76 2377 2550 1074 1082 1940 1931 4399 1719 4758 65 2930 2095 2404 3976 1038 2016 4250 1740 3542 616 3499 1611 3930 3028 969 2176 414 4068 2376 2729 3604 571 4558 3952 4508 1755 1413 1712 3512 2256 4437 1413 4517 4107 324 3033 3695 2482 2151 157 12 4942 1053 4493 4475 1437 977 1775 2830 1217 1385 77 2246 1585 3070 4841 111 1791 4731 3617 732 1018 3416 4003 1019 1436 1921 2074 52 903 2947 3625 1366 1187 2495 695 1715 331 3451 2220 757 4385 3612 2348 1945 351 568 4906 4243 1376 68 238 2098 309 209 490 1053 980 324 441 806 615 4198 4265 2742 529 3561 2898 4729 1198 4885 4447 2347 3379 1129 2589 51 2467 1214 4858 2424 4372 720 4880 1426 266 4294 90 1770 4922 1013 3814 499 1713 1664 4684 42 54 2875 1726 3141 590 511 416 4377 1687 3360 721 4998 4135 2902 4202 2102 1629 2873 2719 1916 4391 4424 2508 3410 1358 2356 1354 1454 3199 376 2979 2261 3836 3644 4674 4888 659 4835 877 1622 2013 2081 4071 2994 3849 2265 698 2654 3209 2293 1338 1241 3486 3087 1240 3677 2600 72 3557 3764 1368 1336 4341 4156 162 4733 1646 3448 4157 3327 1537 2482 4581 1955 4072 1325 3475 207 3665 384 2858 3174 194 3688 1717 971 3573 4972 2944 3 3862 4143 885 2046 1683 4113 3768 4591 2187 2847 1132 2964 730 53 4991 0 636 57 4939 831 143 3522 1303 986 1687 3553 1086 1340 4516 3854 902 339 2582 4310 3708 1515 1708 2443 3605 4552 3249 957 2768 1690 3976 2128 3595 1118 10 3102 771 283 3734 2766 720 161 4552 3445 888 121 3404 3812 3130 4929 4669 4297 2398 4719 4913 4691 75 3304 4191 657 2545 3953 3357 658 4961 4798 851 2146 1330 2369 1291 2435 2501 1413 3237 4818 1554 2515 2830 3028 4340 4437 249 217 2883 369 4514 2256 1097 2425 3478 3139 2312 3473 4742 4524 105 3416 1990 2191 4807 1242 3465 4314 22 4413 4063 4139 3582 226 3642 3849 2389 183 1325 3725 3388 4219 822 1770 2199 3609 286 3443 1211 4937 1726 68 2028 2235 4132 3780 4996 950 1926 4882 2571 112 2990 1181 299 926 479 3312 4347 3606 71 4254 2735 219 4101 1793 4733 369 125 3850 3987 1770 4458 28 4640 3337 388 770 752 3116 1066 4243 1956 119 3385 1802 633 1559 4005 387 4807 732 536 2314 349 3826 1177 2278 2660 2409 1454 487 1521 1132 1885 4068 4374 2224 3511 328 1531 4798 2374 2733 3129 3930 3257 2401 1344 2268 374 3201 3738 3239 4175 1731 2951 4232 2664 3408 2458 713 2367 26 1451 1687 669 4314 3575 3985 3660 2398 2389 4554 2826 2081 3563 625 3021 4387 2024 238 2831 4578 858 4624 2620 1873 3396 2133 4666 1760 2592 2993 2833 4684 2555 1371 1802 4288 1569 1060 3404 3540 678 217 421 4246 4408 2171 502 3550 2329 3621 2347 2039 641 1806 3841 418 4603 1960 4312 3068 1903 2704 763 2756 904 3551 1765 4974 4670 1544 2183 2555 2119 587 1952 2044 3801 121 396 693 3052 1537 3143 4495 2934 3523 1516 2824 4558 4651 289 1070 4517 32 3174 314 3706 3637 294 1514 101 887 1844 1554 262 3200 1930 1292 3559 4452 2574 4925 2279 146

SEARCH KEYS:
3774 3322 2872 1933 1197 626 2380 4340 1774 894 3243 4207 4489 4511 3232 3003 4220 3214 2069 4119

LINEAR SEARCH TEST
Did not find 3774
Did not find 3322
Did not find 2872
Did not find 1933
Did not find 1197
Did not find 626
Did not find 2380
Found 4340 at index 746
Did not find 1774
Did not find 894
Did not find 3243
Did not find 4207
Did not find 4489
Did not find 4511
Did not find 3232
Did not find 3003
Did not find 4220
Did not find 3214
Did not find 2069
Did not find 4119

SORTED SEARCH TEST
Did not find 3774
Did not find 3322
Did not find 2872
Did not find 1933
Did not find 1197
Did not find 626
Did not find 2380
Found 4340 at index 877
Did not find 1774
Did not find 894
Did not find 3243
Did not find 4207
Did not find 4489
Did not find 4511
Did not find 3232
Did not find 3003
Did not find 4220
Did not find 3214
Did not find 2069
Did not find 4119

BINARY SEARCH TEST
Did not find 3774
Did not find 3322
Did not find 2872
Did not find 1933
Did not find 1197
Did not find 626
Did not find 2380
Found 4340 at index 877
Did not find 1774
Did not find 894
Did not find 3243
Did not find 4207
Did not find 4489
Did not find 4511
Did not find 3232
Did not find 3003
Did not find 4220
Did not find 3214
Did not find 2069
Did not find 4119

SUMMARY:
Linear Search Comparisons: 19747
Sorted Search Comparisons: 12425
Binary Search Comparisons: 198
Press any key to continue . . .

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.