C++ Using linked lists, and a numbers.txt, use radix sort and print it to the co
ID: 3880138 • Letter: C
Question
C++
Using linked lists, and a numbers.txt, use radix sort and print it to the console.
Radix sort is a unique sorting algorithm; implement the Radix Sort algorithm. The program needs replace any array based implementation with an array of linked lists (more details below). Use the numbers.txt (shown below) for the numbers to sort.
Specification:
* 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).
* 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.
numbers.txt (this should work if there are many more numbers in the file):
9380
64
21111
11053
27116
23354
13272
21277
233
42453
2
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
void radixsort(int a[], int n)
{
int i, b[MAX], m = a[0], exp = 1;
for (i = 0; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
while (m / exp > 0)
{
int queue[10] = { 0 };
for (i = 0; i < n; i++)
queue[a[i] / exp % 10]++;
for (i = 1; i < 10; i++)
queue[i] += queue[i - 1];
for (i = n - 1; i >= 0; i--)
b[--queue[a[i] / exp % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
#ifdef SHOWPASS
printf(" PASS : ");
radixsort(a, n);
#endif
}
}
int main(int argc, char *argv[])
{
if (argc != 3)
{
printf
("Need two input parameters in the following order: 1. Input file path 2. Number of elements in file ");
return 0;
}
int num_elements = atoi(argv[2]);
int *input_arr = (int *)calloc(num_elements, sizeof(int));
int i;
FILE *fin; // File pointer to read input file
fin = fopen(argv[1], "r"); // Initialize file pointer
for (i = 0; i < num_elements; i++)
{
fscanf(fin, "%d", &(input_arr[i]));
}
radixsort(input_arr, i);
printf(" Array before sorting: ");
for (i = 0; i < num_elements; i++)
printf("%d ", input_arr[i]);
printf(" ");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.