(a) Suppose we r sort to sort the numbers below, a radix of 10. show the g state
ID: 3825644 • Letter: #
Question
(a) Suppose we r sort to sort the numbers below, a radix of 10. show the g state of the sort after pass, after the sorting is complete. second not Numbers to sort (in their initial order): 11, 21 13, 105, 1492, 411, 1776, 1, 6, 2014, 99, 98, 96, Put the result after the second pass here: (b) Analyze the running time complexity of radix sort in a set of 106 strings of English letters (52 26 upper 26 lower cases) up to length 15 per string (c) Given an array A of n integers in the range [1:n suggest an efficient sorting algorithm for A. Justify your selection. Note: You can consider that the number of digits in an integer k represented in base 10 is approximately equal to log10kExplanation / Answer
A)
Given radix sort and radix is : 10.
Numbers are: 13, 105, 1492, 411, 1776, 1 , 6 , 2014, 99 ,98 , 96, 11, 21.
And given that we need result after second pass:
Therefore we need to perform bucket sort for 1’s digits (First pass), and for 10’s digits (second pass).
For arranging in bucket sort for 1’s digit we need to find 10 modulaas of single digit numbers:
Terefore,
We have to perform bucket sortBucket sort of 1’s digit.
First pass
0
1
2
3
4
5
6
7
8
9
411
1
11
21
1492
13
2014
105
1776
6
98
99
After first pass, the sequence is: 411 , 1 , 11 , 21 , 1492 , 13, 2014, 105, 1776, 6, 98, 99
Second pass:
For second pass we need to calculate modulo for 10’s digits:
0
1
2
3
4
5
6
7
8
9
01
105
06
411
11
13
2014
21
1776
98
99
After second pass, the sequence is: 01, 105, 06, 411, 11, 13, 2014, 21, 1776, 98,99.
0
1
2
3
4
5
6
7
8
9
411
1
11
21
1492
13
2014
105
1776
6
98
99
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.