Please help on RADIXSORT! PseudoCode (if necessary): Radix sort Description In t

Question

Please help on RADIXSORT!

PseudoCode (if necessary):

Radix sort Description In this assignment you will implement RadixSort. See the textbook for the pseu do code Input structure You are going to apply RadixSort to sort vectors. The input starts with an integer number which indicates the number of vectors to be sorted. Then vectors follow, one vector per line. Each vector consists of 10 numbers where each number has a value in t0, 1, 2, 3 Entries of a vector are separated by a space. Output structure Output the sorted sequence of vectors, one per line. Vector i must appear before vector j in your output if and only if for some d E {1,2, 10 vector i is smaller than or equal to vector i on the dth entry. and the two vectors are equal for any of the first d-1 entries. Examples of input and output Input 3 3 3 3 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 1 300 2 1 0 0 0 0 1 300 2 2 0 0 0 0 2 3 2 1 2 2 2 2 2 2 Output 2 3:2: 1:2 2:2 2 2 2 2 3:2:2:2; 2:2 2:2 2 3; 3; 3 3; 3 2;2; 2;2; 2; More precisely, the above output example has 6 lines since a "cout endli" call was made at the end of each of the first 5 lines; those are the only white characters.

Explanation / Answer

#include<stdio.h>

int getMax(int arr[], int n) {
int mx = arr[0];
int i;
for (i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

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]++;

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]--;
}

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) {
int m = getMax(arr, n);

int exp;
for (exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}

void print(int arr[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}

int main() {
int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
int n = sizeof(arr) / sizeof(arr[0]);
radixsort(arr, n);
print(arr, n);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.