Question

Write a program that compares the execution speed of two different sorting algorithms: bubble sort and selection sort. It should do this via functions you must write with the following prototypes:

void setRandomValues(int[], int[], int length);

This function sets two integer arrays with identical random values. The first two arguments are two integer arrays of the same length, and the third argument is the length of those arrays. The function then sets each element in the first and second argument arrays to a random value between(which includes) 1 and the array length value. When the function is done, both the first and second argument arrays should have exactly the same(random) values.

void bubbleSort(int[], int length);

This function performs a bubble sort on the argument integer array of the argument length size. When the function is done, the argument array will be sorted. You can use the sorting C++ code in the textbook here.

void selectionSort(int[], int length);

This function performs a selection sort on the argument integer array of the argument length size. When the function is done, the argument array will be sorted. You can use the sorting C++ code in the textbook here.

void compareBubbleAndSelectionSort(int length);

This function performs the following actions:

1. Prints that it is comparing sorting functions for a list of size length.
2. Calls setRandomValues to generate two identical random arrays of the argument length size.
3. Uses the ctime library to get the current time in seconds(time(0)) and saves it.
4. Calls bubbleSort on the first random array.
5. Again uses the ctime library to get the current time in seconds(time(0) and saves it.
6. Prints the number of seconds it took to bubble sort the array.
7. Uses the ctime library to get the current time in seconds(time(0) and saves it.
8. Calls selectionSort on the second random array.
9. Again uses the ctime library to get the current time in seconds(time(0) and saves it.
10. Prints the number of seconds it took to selection sort the array.

The output of the function should look something like this:

Comparing bubble and selection for a list of size 25000

Bubble sort took 3 second(s).

Selection sort took 1 second(s).

The program should then call compareBubbleAndSelectionSort with 25000, 50000, and 100000 length values.

Answer 1

Here is your required code in C++

#include <bits/stdc++.h>

using namespace std;

// to swap two values
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
  
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
  
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

void selectionSort(int arr[], int n)
{
int i, j, min_idx;
  
// 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;
  
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}

// generate two arrays with random values
void setRandomValues(int a[], int b[], int length)
{
srand(time(0));
  
for(int i=0;i<length;i++)
{
//generate randm value from 1 to length
int x = rand()%length + 1;
a[i] = x;
b[i] = x;
}

}

// to compare time used by two different sorts
void compareBubbleAndSelectionSort(int length)
{
// output
cout<<"Comparing bubble and selection for a list of size "<<length<<endl;
  
int a[length], b[length];
  
//settting random values for both arrays
setRandomValues(a,b, length);
time_t curtime;
  
int t1, t2;
  
//storing time before sorting
t1 = time(0);
bubbleSort(a, length);
//storing time after sorting
t2 = time(0);
//output the time difference
cout<<"Bubble sort took "<<t2-t1<<" second(s)."<<endl;
  
//storing time before sorting
t1 = time(0);
selectionSort(b, length);
//storing time after sorting
t2 = time(0);
//output the time difference
cout<<"Selection sort took "<<t2-t1<<" second(s)."<<endl;
}

//driver code
int main()
{
//testing for different values of length
cout<<endl;
compareBubbleAndSelectionSort(25000);
cout<<endl;
compareBubbleAndSelectionSort(50000);
cout<<endl;
compareBubbleAndSelectionSort(100000);
  
return(0);
}

Please refer to the screenshot of the code to understand the indentation of the code:

Here is the Output for the sample Test Cases: