search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[QZ#3] MSD Input #55

Closed lcunild closed 4 years ago

lcunild commented 4 years ago

Will the integers be the same length? If not, does the MSD algorithm start by sorting the numbers using the most significant digit of each integer, or by starting at the maximum digit of any integer? For example, if the inputs were 1 and 103, would these both be sorted into the same bucket after the first pass, as their most significant digit is both 1, or should 1 be considered to have leading zeros, to make the integers the same length?

lujiaying commented 4 years ago

Will the integers be the same length?

No. If yes, then the MSD algorithm is too limited, and not useful.

does the MSD algorithm start by sorting the numbers using the most significant digit of each integer, or by starting at the maximum digit of any integer?

I think this part is the most important concept for implementing MSD algorithm. If I tell you the answer directly, it is like show the solution. Instead, I would encourage to test the two alternative way you proposed by mimicking the LSD Radix Sort process (https://speakerdeck.com/emory/dsa-java-lsd-radix-sort). Then it is possible to figure out which one is preferable.

jdchoi77 commented 4 years ago

@lcunild the input length varies by every key; you need to sort with the most-significant digit first then move down to the 2nd-most significant digit, and so on as we discussed in the class.