Write one C++ program in beginner terms that will accomplish both programming ch
ID: 3876503 • Letter: W
Question
Write one C++ program in beginner terms that will accomplish both programming challenges.
Create two arrays where each will hold the contents of a file (random.txt) of 200 integer values. Using the two arrays, call a function that uses the bubble sort algorithm to sort one of the arrays in ascending order. The function should count the number of exchanges it makes.
The program should then call a function that uses the selection sort algorithm to sort the other array. It should also count the number of exchanges it makes. Display these values. Next, call a function that uses the linear search program to locate the value 869. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the numbers of comparisons it makes. Display these values. the contents of random.txt are:
42 468 335 501 170 725 479 359 963 465 706 146 282 828 962 492 996 943 828 437 392 605 903 154 293 383 422 717 719 896 448 727 772 539 870 913 668 300 36 895 704 812 323 334 674 665 142 712 254 869 548 645 663 758 38 860 724 742 530 779 317 36 191 843 289 107 41 943 265 649 447 806 891 730 371 351 7 102 394 549 630 624 85 955 757 841 967 377 932 309 945 440 627 324 538 539 119 83 930 542 834 116 640 659 705 931 978 307 674 387 22 746 925 73 271 830 778 574 98 513 987 291 162 637 356 768 656 575 32 53 351 151 942 725 967 431 108 192 8 338 458 288 754 384 946 910 210 759 222 589 423 947 507 31 414 169 901 592 763 656 411 360 625 538 549 484 596 42 603 351 292 837 375 21 597 22 349 200 669 485 282 735 54 1000 419 939 901 789 128 468 729 894 649 484 808 422 311 618 814 515
Explanation / Answer
void bubbleSort(int arr[], int n)
{
int i, j, count=0;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j]= arr[j+1];
arr[j+1]=temp;
count ++;
}
cout << "The number of swaps were "<< count;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx, count=0;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
{
int temp = arr[i];
arr[i]= arr[min_idx];
arr[min_idx]=temp;
count ++;
}
// Swap the found minimum element with the first element
}
cout << "The number of swaps were "<< count;
}
int linearSearch(int arr[], int n, int x)
{
int i, count=0;
for (i=0; i<n; i++)
if (arr[i] != x)
count++;
if (arr[i] == x)
cout << "The number of comparisons were "<< count+1;
break;
return -1;
}
// C program to implement recursive Binary Search
#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{ int count=0;
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] != x)
coutn++;
return mid;
if (arr[mid] == x)
cout << "The number of comparisons were "<< count+1;
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
// C program to implement recursive Binary Search
#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{ int count=0;
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] != x)
coutn++;
return mid;
if (arr[mid] == x)
cout << "The number of comparisons were "<< count+1;
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.