Answer Happy

Use MSD radix sort to Sort the numbers in alphabetical(lexicographical) order. This is what i have so far. #include

Posted: Fri May 20, 2022 6:17 pm

by answerhappygod

Use MSD radix sort to Sort the numbers in
alphabetical(lexicographical) order.
This is what i have so far.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <list>
using namespace std;
// Function to get the largest element from an array
int getMax(vector<int>
&array, int n) {
int max = array[0];
for (int i = 1; i <
n; i++)
if (array > max)
max = array;
return max;
}
// Using counting sort to sort the elements in the basis of
significant places
void
countingSort(vector<int> &array,
int size, int place) {
const int max = 10;
int output[size];
int count[max];
for (int i = 0; i <
max; ++i)
count = 0;
// Calculate count of elements
for (int i = 0; i <
size; i++)
count[(array / place) % 10]++;
// Calculate cumulative count
for (int i = 1; i <
max; i++)
count += count;
// Place the elements in sorted order
for (int i = size - 1;
i >= 0; i--) {
output[count[(array / place) % 10] - 1] =
array;
count[(array / place) % 10]--;
}
for (int i = 0; i <
size; i++)
array = output[i];
}
// Main function to implement radix sort
void
radixsort(vector<int> &array,
int size) {
// Get maximum element
int max = getMax(array, size);
// Apply counting sort to sort elements based on place
value.
for (int place = 1; max
/ place > 0; place *= 10)
countingSort(array, size, place);
}
// Print an array
void
printArray(vector<int> &array,
int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver codes
int main() {
vector<int> array = {121, 432,
564, 23, 1, 45, 788};
int n = sizeof(array) /
sizeof(array[0]);
radixsort(array, n);
printArray(array, n);
}
EXPECTED OUTPUT: 1, 121, 23, 432, 45, 564,
788