Question

c++

Implement Radix Sort Most sorting algorithms, like bubble, insertion, selection and shell follow similar implementations. Radix sort is a unique sorting algorithm. In this assignment, implement the Radix Sort algorithm, as explained the text book in chapter 2. Use the Numbers.txt file in the DataFiles folder for the numbers to sort. Extra credit is available for processing alphabetic strings instead of just numbers. Specification: * Using your Doubly-Linked list to create an dynamic array of Doubly-Linked lists (like lab1). The array should be 10 in length to satisfy the number of digits in Base10. * The 10 positions in the array of LinkedList are used for each base 10 radix. In mathematical numeral systems, the radix or base is the number of unique digits, including zero, used to represent numbers in a positional numeral system. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9. * Read the Numbers.txt file and sort them using the Radix Sort algorithm.

Answer 1

Radix sort Proram

// C++ implementation of Radix Sort

#include<iostream>

using namespace std;

// A utility function to get maximum value in arr[]

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

}

// Driver program to test above functions

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;

}

Radix Sort

The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc) is Ω(nLogn), i.e., they cannot do better than nLogn.

Counting sort is a linear time sorting algorithm that sort in O(n+k) time when elements are in range from 1 to k.