RADIX SORT MUST READ IN N AMOUNT OF INTEGERS! MEANING ANY AMOUNT OF INTEGERS, NU
ID: 3677336 • Letter: R
Question
RADIX SORT MUST READ IN N AMOUNT OF INTEGERS! MEANING ANY AMOUNT OF INTEGERS, NUMBER OF INTEGERS IS UNSPECIFIED
You will write an C program implementation of radix sort which behaves as follows » It reads a sequence of non-negative integers from standard input. The number of values to be read (N) is not given to you ahead of time » The program reads non-negative integers until it reaches EOF or an attempt to read an unsigned int fails (e.g., there is a "token" in the input that cannot be parsed as a non-negative integer) In the latter case, the program itself does not "fail"; it simply sorts the values it did successfully read. . Sorts them using Radix Sort with a radix of N (or near N -- more on this below) » Displays the data in sorted order.Explanation / Answer
Radix sort:
Radix sort is an algorithm. Radix Sort sorts the elements by processing its individual digits. Radix sort processing the digits either by Least Significant Digit(LSD) method or by Most Significant Digit(MSD) method.
The Radix Sort Algorithm1) Do following for each digit i where i varies from least significant digit to the most significant digit.a) Sort input array using counting sort (or any stable sort) according to the i’th digit.
Example:
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1s place) gives: [*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]
170, 90, 802, 2, 24, 45, 75, 66
Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
Time complexity:Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be O(logb(k)). So overall time complexity is O((n+b)*logb(k)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes O(nLogb(n)). But it still doesn’t beat comparison based sorting algorithms.
/*
* C Program to Sort an Integer Array using LSDRadix Sort Algorithm
*/
#include <stdio.h>
int min = 0, count = 0, array[100] = {0}, array1[100] = {0};
void main()
{
int k, i, j, temp, t, n;
printf("Enter size of array :");
scanf("%d", &count);
printf("Enter elements into array :");
for (i = 0; i < count; i++)
{
scanf("%d", &array[i]);
array1[i] = array[i];
}
for (k = 0; k < 3; k++)
{
for (i = 0; i < count; i++)
{
min = array[i] % 10; /* To find minimum lsd */
t = i;
for (j = i + 1; j < count; j++)
{
if (min > (array[j] % 10))
{
min = array[j] % 10;
t = j;
}
}
temp = array1[t];
array1[t] = array1[i];
array1[i] = temp;
temp = array[t];
array[t] = array[i];
array[i] = temp;
}
for (j = 0; j < count; j++) /*to find MSB */
array[j] = array[j] / 10;
}
printf("Sorted Array (lSdradix sort) : ");
for (i = 0; i < count; i++)
printf("%d ", array1[i]);
}
Sample output:
Enter size of array :7
Enter elements into array :170
45
90
75
802
24
2
Sorted Array (ladradix sort) : 2 24 45 75 90 170 802
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.