Question

Test each algorithm (Counting Sort, Radix Sort, and Bucket Sort algorithms) on three different arrays of 1000 elements each with the following properties:

By the way: To perform bucket sort the right way, convert the array elements to a value between 0 and 1

Array1: integers only in the range 0 through 999, already sorted in increasing order

Array2: integers only in the range 0 through 999, already sorted in decreasing order

Array3: integers only in the range 0 through 999, randomly generated

Please include your program *source code AND output* as part of your submission for this question.

1. Measure the runtime of each algorithm on each array.

2. Compare the runtime performances you've obtained in 3A and comment on them.

Please do not copy the other answers to be at risk of being downvoted. You can use C++. I mainly need a clear explanation on how each runtime compares (please don't use others' answers for this part either, or it will get downvoted).

Answer 1

SOLUTION-

1) I have solve the problem in C++ code with comments and screenshot for easy understanding :)

CODE-

#include <bits/stdc++.h>
using namespace std;

//Define the maximum size of the array.
#define MAX_SIZE 1000

//Define the Counting_sort.
void Counting_Sort(int arr[], int n, int a, int b)
{
//Declare the variables.
int i, j = 0, temp_array[a] = {0};
  
//Count the occurence of the elements of the array.
for(i=0; i<n; i++)
temp_array[arr[i]-b]++;
  
//Initialize the variable i;
i=0;
  
//Insert the elements in the array.
while(i < a)
{
checkpoint:
arr[j] = b+i;
j++;
temp_array[i]--;
  
// place the a[i] until count is 0
if(temp_array[i] > 0)
goto checkpoint;
  
i++;
}
}

//Define the function find_max
//to get the maximum.
int find_max(int array[], int n)
{
//Assign the first element of the array to the variable max.
int max = array[0];
  
//Begin the for loop.
for (int i = 1; i < n; i++)
  
//Compare the array elements with the max value.
if (array[i] > max)
  
//Assign the value at the i index
//to the variable max.
max = array[i];
  
//Return the variable max.
return max;
}

//Define the helper function.
void helper(int arr[], int n, int exponent)
{

//Declare the arrays and the variables.
int ans[n], i, count[10] = {0};

for (i = 0; i < n; i++)
count[(arr[i] / exponent) % 10]++;
  
//Begin the loop and compute the cummulative count.
for (i = 1; i < 10; i++)
count[i] += count[i-1];

for (i = n - 1; i >= 0; i--)
{
ans[count[(arr[i] / exponent) % 10] - 1] = arr[i];
count[(arr[i] / exponent) % 10]--;
}

// Assigning the result to the arr pointer of main().
for (i = 0; i < n; i++)
arr[i] = ans[i];
}

//Define the Radix_sort.
void Radix_sort(int arr[], int n)
{
//Declare the variables.
int exponent, m;
  
//Call the function to get the maximum value.
m = find_max(arr, n);

//Call the function helper_function.
for (exponent = 1; m/exponent > 0; exponent *= 10)
helper(arr, n, exponent);
}

//Define the Bucket_sort().
void Bucket_sort(int a[], int n)
{
//Declare the variable.
int i, j, k, bucket[1000];
  
//Begin the for loop to initialize the buckets.
for(i = 0; i < 1000; ++i)
bucket[i] = 0;
  
//Begin the loop to fill the buckets.
for(i = 0; i < n; ++i)
++bucket[a[i]];
  
//Sort the filled bucket using the counting sort.
for(i = 0, j = 0; j < 1000; ++j)
for(k = bucket[j]; k > 0; --k)
a[i++] = j;
}

//Define the main function.
int main()
{
//Declare the clock variables.
clock_t start,end;
  
//Seed the generation of the random numbers.
srand(time(NULL));
  
//Declare the variables.
double time_spent;
int array[1000],b[1000], i, number,n;
  
//Begin the for loop and generate the random numbers.
for(i = 0; i < 1000; i++)
{
  
//Generate the random numbers.
number=rand()%1000;
array[i]=number;
b[i]=number;
  
}
  
//Display the statement.
cout<<"The time of sorting techniques for Array 1:"<<endl;
sort(array,array+1000);
  
//Begin the clock now.
start=clock();
  
//Call the counting sort.
Counting_Sort(array,1000,1000,0);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by counting sort for Array1.
cout<<"Counting sort :"<<time_spent<<" ms"<<endl;
  
//Begin the clock now.
start=clock();
  
//Call the radix_sort().
Radix_sort(array,1000);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by Radix sort for Array1.
cout<<"Radix sort :"<<time_spent<<" ms"<<endl;
  
start=clock();
  
//Call the bucket_sort().
Bucket_sort(array,1000);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;

//Display the time taken by Bucket sort for Array1.
cout<<"Bucket sort :"<<time_spent<<" ms"<<endl;
  
  
/***********Array 2***********************/
  
for(i = 0; i < 1000; i++)
{
number=rand()%1000;
array[i]=number;
b[i]=number;
  
}
  
//Display the statement.
cout<<"The time of sorting techniques for Array 2:"<<endl;
sort(array,array+1000);
reverse(array,array+n);
  
//Begin the clock now.
start=clock();
  
//Call the counting sort.
Counting_Sort(array,1000,1000,0);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by counting sort for Array2.
cout<<"Counting sort :"<<time_spent<<" ms"<<endl;
  
//Begin the clock now.
start=clock();
  
//Call the radix_sort().
Radix_sort(array,1000);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by Radix sort for Array2.
cout<<"Radix sort :"<<time_spent<<" ms"<<endl;
  
//Begin the clock now.
start=clock();
  
//Call the bucket_sort().
Bucket_sort(array,1000);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by Bucket sort for Array2.
cout<<"Bucket sort :"<<time_spent<<" ms"<<endl;
  
  
/*********************Array 3************/
  
for(i = 0; i < 1000; i++)
{
  
number=rand()%1000;
array[i]=number;
b[i]=number;
  
}
  
//Display the statement.
cout<<"The time of sorting techniques for Array 3:"<<endl;
  
//Begin the clock now.
start=clock();
  
//Call the counting sort.
Counting_Sort(array,1000,1000,0);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by counting sort for Array3.
cout<<"Counting sort :"<<time_spent<<" ms"<<endl;
  
//Begin the clock now.
start=clock();
  
//Call the radix_sort().
Radix_sort(array,1000);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by Radix sort for Array3.
cout<<"Radix sort :"<<time_spent<<" ms"<<endl;
  
//Begin the clock now.
start=clock();
  
//Call the bucket sort.
Bucket_sort(array,1000);
  
//Now end the clock.
end=clock();
  
//Computing the difference of the start and the end time.
time_spent=(double)(end-start)/CLOCKS_PER_SEC;
  
//Convert the difference in milliseconds.
time_spent=time_spent*1000.0;
  
//Display the time taken by Bucket sort for Array3.
cout<<"Bucket sort :"<<time_spent<<" ms"<<endl;
  
//Return the value for the main function.
return 0;

}

SCREENSHOT-

2)

The comparison of the sorting techniques as per the sample output obtained is given as follows:

As per the first array, the time complexity of the sorting techniques is in the following order:

Bucketsort (0.018 ms) < Countingsort (0.019 ms) < Radixsort (0.138 ms)

As per the second array, the time complexity of the sorting techniques is in the following order:

Bucketsort (0.019 ms) < Countingsort (0.021 ms) < Radixsort (0.134 ms)

As per the third array, the time complexity of the sorting techniques is in the following order:

Bucketsort (0.02 ms) < Countingsort (0.021 ms) < Radixsort (0.132 ms)

Hence, on average the counting and the bucket sort are doing better as compared to the radix sort.

Since, after every execution, the output will be different, but the performance of the bucket and the counting sort is always better than the radix sort.

Thus, among the three sorting techniques, the better sorting techniques to use are bucket and counting.

IF YOU HAVE ANY DOUBT PLEASE COMMENT DOWN BELOW I WILL SOLVE IT FOR YOU:)
----------------PLEASE RATE THE ANSWER-----------THANK YOU!!!!!!!!----------