Question

Please use C++ Create a program that generates an array of sizes n= 10, 100, 500,...

Please use C++

Create a program that generates an array of sizes n= 10, 100, 500, 5000 and 25000 items. Your program should populate those arrays with randomly generated integers with a value between 0 and the 2n where n is the size of the array. Create an implementation for the following sort operations.

Count Sort

Radix-sort

0 0
Add a comment Improve this question Transcribed image text
Answer #1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
  
// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
int output[n]; // output array
int i, count[10] = {0};
  
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
  
// Change count[i] so that count[i] now contains actual
// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
  
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
  
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
  
// The main function to that sorts arr[] of size n using
// Radix Sort
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
  
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
  
// A utility function to print an array
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main() {
int arr1[]={10,100,500,5000,25000};
srand(time(NULL));
for(int i=0;i<5;i++)
{
int n=arr1[i];
cout<<"For n="<<n<<endl<<endl;
int arr[n+1]; //create an array with given number of elements
for(int i = 0; i<n; i++) {
arr[i]=rand()%(2*n+1);

}
cout << "Array before Sorting: ";
print(arr, n);
radixsort(arr, n);
cout << "Array after Sorting: ";
print(arr, n);
}
}

Kindly revert for any queries

Thanks.

Add a comment
Know the answer?
Add Answer to:
Please use C++ Create a program that generates an array of sizes n= 10, 100, 500,...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • DESCRIPTION Implement a program in C++ that generates a specified number of random integers, records them...

    DESCRIPTION Implement a program in C++ that generates a specified number of random integers, records them in three arrays, then sorts the arrays with Insertion Sort, Merge Sort, and Quick Sort, respectively. Augment the three sorting algorithms with counters and report the number of characteristic operations each performs in sorting the (same) random values. INPUT The program reads from the terminal the number of random integers to generate, a seed value for the pseudo-random number generator, and a character that...

  • Write a computer program that prompts the user for one number, n for the number of...

    Write a computer program that prompts the user for one number, n for the number of items in the array to sort, and create and sort 1000 different arrays of this size timing the run to get an average time to sort an array of this size. Then do the following: Initiate a variable running_time to 0 Create a for loop that iterates 1000 times. In the body of the loop, Create an array of n random integers (Make sure...

  • In JAVA please (need answers in a few hours!) Exercise #2: Design and implement a program...

    In JAVA please (need answers in a few hours!) Exercise #2: Design and implement a program (name it SimpleSort) to implement and test the three sort algorithms (Bubble, Insertion, Selection) discussed in the lecture slides. Define method BubbleSort() to implement Bubble sort of an array of integers. Modify the algorithm implementation to count number of swaps it takes to sort the array. Define method InsertionSort() to implement insertion sort of an array of integers. Modify the algorithm implementation to count...

  • C++ Search & Sort

    Exercise #2: Design and implement a program (name it SimpleSort) to implement and test the three sort algorithms (Bubble, Insertion, Selection) discussed in the lecture slides.  Define method BubbleSort() to implement Bubble sort of an array of integers. Modify the algorithm implementation to count number of swaps it takes to sort the array.  Define method InsertionSort() to implement insertion sort of an array of integers. Modify the algorithm implementation to count number of swaps it takes to sort the array. Define...

  • Create sets of integers with the following characteristics with array sizes of 100,000, 500,000 and 1000,000...

    Create sets of integers with the following characteristics with array sizes of 100,000, 500,000 and 1000,000 1. Set where no integer is repeated 2. Set where the range is low and the integers repeat Compare the performances of the following sorting algorithms. You can either write the algorithms on your own or modify algorithms obtained from elsewhere. Create a table with the rows being the different algorithms and the columns being the inputs. Run each input 10 times and report...

  • Write a C++ program that will create an array with a given number of elements. Use...

    Write a C++ program that will create an array with a given number of elements. Use size = 10 for demonstration purposes, but write the program where the size of the array can be changed by changing the value of one constant. Fill the array with random numbers between 0 and 100. Write the program to perform the following operations: 1. Find and display the largest value in the array. 2. Find and display the smallest value in the array....

  • Write a c++ program that does the following Create an integer array of size 30. Assign...

    Write a c++ program that does the following Create an integer array of size 30. Assign -1 to each location in the array indicating that the array is empty. Populate half of the array with random integer values between 100 and 500 inclusive. Use the following formula in order to hash and store each number in its proper position/location. Generated Number Table Size: Should a collision occurs, use linear probing to find next available position location. Use the following probing...

  • Be sure to include the number of total swaps in each sort. Create a total_Time variable...

    Be sure to include the number of total swaps in each sort. Create a total_Time variable is the total time it takes all 1000 iterations to run. DO NOT INCLUE THE TIME IT TAKES TO GENERATE A UNIQUE RANDOM ARRAY EACH LOOP. In java, Write a computer program that prompts the user for one number, n for the number of items in the array to sort and create and sort 1000 different arrays of this size,  timing the run to get...

  • PLEASE DO BOTH #5 AND #6. The purpose of the project is to perform a timing...

    PLEASE DO BOTH #5 AND #6. The purpose of the project is to perform a timing experiment. You are required to complete the following activities: Write a computer program that prompts the user for a number, creates an array for that number of random integers, and then usees the bubble sort to order the array. The program should print out the array prior to the call to the sorting algorithm and afterwards. You can write the program in either Java,...

  • Write a program in Java that obtains the execution time of selection sort, insertion sort, bubble...

    Write a program in Java that obtains the execution time of selection sort, insertion sort, bubble sort, merge sort, quick sort, and radix sort. Your program should test all sort methods for input sizes of 10000, 20000, 30000, 40000, 50000, and 60000. The selection sort, bubble sort, and radix sort should also be tested for input sizes 100000 and 200000. Your program should create the data that is sorted from randomly generated integers and should output the results in a...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT