The following pseudocode describes the algorithm for a radix sort of n decimal i
ID: 3776830 • Letter: T
Question
The following pseudocode describes the algorithm for a radix sort of n decimal integers of d digits each: radixSort(theArray: ItemArray, n: integer, d: integer): void for (j = d down to 1) { Initialize 10 groups to empty Initialize a counter for each groups to 0 for (i = 0 through n – 1) { K = jth digit of theArray[i] Place theArray[i] at the end of group k Increase kth counter by 1 } Replace the items in theArray with all the items in group 0, Followed by all the items in group I, and so on. } } a) Write a function called radixsort that sorts its array parameter using the above radix sort algorithm. b) Calculate and print the number of comparisons, to verify it is in Big-O(n) c) Write a main() function to test a worst, an averaged and a best cases in terms of time efficiency
Explanation / Answer
#include <iostream>
#include <cstdlib>
using namespace std;
// countingsort function of arr[]
void countSort(int arr[], int n, int exp)
{
int sortedArr[n];
int i, count[10] = {0};
int no_of_comp=0;
for (i = 0; i < n; i++){
count[(arr[i] / exp) % 10]++;
}
// actual position of this digit in sortedArr[]
for (i = 1; i < 10; i++){
count[i] += count[i - 1];
}
//building final array
for (i = n - 1; i >= 0; i--)
{
sortedArr[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
//coping sorted array to arr
for (i = 0; i < n; i++)
arr[i] = sortedArr[i];
}
// Radix Sort function to sort the array
void radixsort(int arr[], int n,int d)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
/*
* Main
*/
int main()
{
int n=8;
int d=3;
int arr[] = {170, 405, 705, 900, 802, 234, 268, 667};
cout<<" Items in the array before sorting are:";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
radixsort(arr, n,d);
cout<<" Items in the array after sorting are:";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.