(C++) Using linked lists and numbers from numbers.txt, use radix sort and print
ID: 3880825 • Letter: #
Question
(C++) Using linked lists and numbers from numbers.txt, use radix sort and print the sorted numbers to the console.
Specification:
Radix sort is a unique sorting algorithm; implement the Radix Sort algorithm. Use the numbers.txt (shown below) for the numbers to sort.
* Convert your linked list code (https://www.chegg.com/homework-help/questions-and-answers/c-write-program-reads-list-words-wordstxt-file-shown-stores-singly-linked-list-prints-word-q26295882) to have a 'prev' AND 'next' pointer (or object). (DoublyLinkedList)
* Use the DynamicArray from (https://www.chegg.com/homework-help/questions-and-answers/c-using-pseudo-code-listed-extend-include-reading-data-strings-file-convert-int-based-cont-q26217211) to make a dynamic array of SinglyLinkedLists (use your now DoublyLinkedList - use the next, rather than prev, node).
* 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.
* Output the sorted numbers to the console.
numbers.txt (this should work if there are many more numbers in the file):
9380
64
21111
11053
27116
23354
84938
21277
233
42453
2
4324
Explanation / Answer
#include <iostream>
#include <fstream> // (input file stream)
#include <iomanip>
using namespace std;
// function to get maximum value in arr[]
int getMaximum(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMaximum(arr, n);
// use count sort for every digit. pass the exp(j) of the number. j is 10^i
// where i is current digit number
for (int j = 1; m/j > 0; j *= 10){
int out[n]; // output array
int i;
int count[10] = {0};
// Store frequencies in count[] array
for (i = 0; i < n; i++)
count[ (arr[i]/j)%10 ]++;
// Change count[i] so that count[i] now contains actual
// position of this digit in out[] array
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--)
{
out[count[ (arr[i]/j)%10 ] - 1] = arr[i];
count[ (arr[i]/j)%10 ]--;
}
for (i = 0; i < n; i++)
arr[i] = out[i];
}
}
int main() {
// your code goes here
ifstream inFile; //declare a input file stream variable
inFile.open("numbers.txt"); // open the file numbers.txt
if (!inFile) {
cout << "Unable to open file";
exit(1); // terminate with error
}
vector <int> ar;
int x;
while (inFile >> x) { // take the values from file in int x
ar.push_back(x);
}
radixsort(ar, n);
inFile.close(); // close the file
for(int i=0; i<n; i++)
cout<<ar[i]<<" ";
return 0;
}
Output : 2, 64, 233, 4324, 9380, 11053, 21111, 21277, 23354, 27116, 42453, 84938
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.