Question

7. (14 points) Use LSD-first Radix Sort algorithm to sort the following array of numbers. Write the worst case, the best case time complexity and discuss if these sorting algorithms are stable and in-place? In what cases using these algorithms would not be efficient? (You must run Counting Sort for each digit explicitly.) A=[22,15,16,13,23,45,0,23,123]

Answer 1

Solution:

solution LSD - first means Least Significant Digst first where let us take plumber 104 B one's place ten's place hundred's place In this sorting the sorted in by sorting one! array will be place first then 11 So 'Ten's place" then The given array A= (22, 15, 16, 13, 23, 450, 23, 123 firs one's places sorted = [0, 22, 13, 23, 23, 123, 15, 45, 16] 1 q'ì'îîn 11 Now ten's places sorted = [0, 13, 15, 16, 22, 23, 23, 123, 45] hundreds's places sorted now [0, 13, 15, 16, 22, 23, 23, 45, 123

123 size 3 n In above list 8 23 given two of the time complexity of this sorting in worst case is o (wn) where W = element size (: input size (in given array size is 9) In best case and average case also time complexity is o (wh) where the iteration need to it array sorted be done to check if sorted or not. LSO- radix soft algorithm is stable if two elements are some there the place elements won't be Changed Where to EX: times 23, 23 I's and hot to be according lo's places the digit need changed

- If the array contains single-digit humber and more -digit numbers iterations has to this case this algorithm is in-efficient there be more In Ex? [89765, 1 y single digit neubber five digit number Here algorithm og iterates upto Ten thousand's place where other one has only one's place Thank you, Have a great day