COMMENT ON the code below .what does each part do for the program? #include <ios
ID: 3880836 • Letter: C
Question
COMMENT ON the code below .what does each part do for the program?
#include <iostream>
#include <fstream>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}
void bubbleSort(int numbers[], int n)
{
int i, j, count = 0;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (numbers[j] > numbers[j+1]){
swap(&numbers[j], &numbers[j+1]);
count++;
}
cout << "No of exchanges in bubble sort is " << count << endl;
}
void selectionSort(int numbers2[], int n)
{
int i, j, min_idx, count = 0;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (numbers2[j] < numbers2[min_idx])
min_idx = j;
swap(&numbers2[min_idx], &numbers2[i]);
count++;
}
cout << "No of exchanges in selection sort is " << count << endl;
}
void linearSearch(int numbers[]){
int count = 0;
for(int i = 0; i < 200; i++){
count++;
if(numbers[i] == 869)
break;
}
cout << "No of comparisons in linear search is " << count << endl;
}
int binarySearch(int numbers[], int l, int r, int x, int count)
{
if (r >= l)
{
count++;
int mid = l + (r - l)/2;
if (numbers[mid] == x)
return count;
if (numbers[mid] > x)
return binarySearch(numbers, l, mid-1, x, count);
return binarySearch(numbers, mid+1, r, x, count);
}
return -1;
}
int main()
{
fstream myfile("data.txt", std::ios_base::in);
int a, numbers[200], count = -1;
while (myfile >> a)
{
count++;
numbers[count] = a;
}
int numbers2[200];
for(int i = 0; i < 200; i++)
numbers2[i] = numbers[i];
bubbleSort(numbers, 200);
selectionSort(numbers2, 200);
linearSearch(numbers);
int res = binarySearch(numbers,0, 199, 869, 0);
cout << "No of comparisons in binary search is " << res << endl;
return 0;
}
Explanation / Answer
/* Importing headers(libraries) required */
#include <iostream>
#include <fstream>
using namespace std;
/* A Function for swapping two integeres by reference */
void swap(int *xp, int *yp)
{
/*Note that the addresses of the integers are getting swapped */
int temp = *xp;
*xp = *yp;
*yp = temp;
}
/*A function to print all the elements of the array using a for loop,given the size of the loop */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}
/* This part sorts the array using bubble sort.The basic algorithm which repeatedly sorts the adjacent elements if they are in the wrong order.
Note that there are two for loops so that every element in the array is compared with every other element.*/
void bubbleSort(int numbers[], int n)
{
int i, j, count = 0;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
/*Checking if greater than the number front of it */
if (numbers[j] > numbers[j+1])
/* Swapping if greater*/
{
swap(&numbers[j], &numbers[j+1]);
count++;
}
cout << "No of exchanges in bubble sort is " << count << endl;
}
/*This does Selection sort.This type of sort maintains two types of arrays.Sorted and and unsorted.algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1)The subarray which is already sorted.
2) Remaining subarray which is unsorted
*/
void selectionSort(int numbers2[], int n)
{
int i, j, min_idx, count = 0;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (numbers2[j] < numbers2[min_idx])
min_idx = j;
swap(&numbers2[min_idx], &numbers2[i]);
count++;
}
cout << "No of exchanges in selection sort is " << count << endl;
}
/*This is a normal kind of search in which we check every element to find a match.Here For Example we are searching for 869 using a for loop*/
void linearSearch(int numbers[]){
int count = 0;
for(int i = 0; i < 200; i++){
count++;
if(numbers[i] == 869)
break;
}
cout << "No of comparisons in linear search is " << count << endl;
}
/*Wow,This is a great algorithm to search for an element in the array. */
int binarySearch(int numbers[], int l, int r, int x, int count)
{
/* l is left,r is right*/
if (r >= l)
{
count++;
/*Finding the middle element of the array*/
int mid = l + (r - l)/2;
/*Comparing if the middle element is greater ,lesser or equal*/
if (numbers[mid] == x)
return count;
if (numbers[mid] > x)
/* Using recursion to search for the element either on the left or right part of the array */
return binarySearch(numbers, l, mid-1, x, count);
return binarySearch(numbers, mid+1, r, x, count);
}
return -1;
}
/*This is the main function to run all the previous defined functions*/
int main()
{
fstream myfile("data.txt", std::ios_base::in);
int a, numbers[200], count = -1;
while (myfile >> a)
{
count++;
numbers[count] = a;
}
int numbers2[200];
for(int i = 0; i < 200; i++)
numbers2[i] = numbers[i];
bubbleSort(numbers, 200);
selectionSort(numbers2, 200);
linearSearch(numbers);
int res = binarySearch(numbers,0, 199, 869, 0);
cout << "No of comparisons in binary search is " << res << endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.