Skip to content

Bug report for radix sort #336

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
InnoFang opened this issue Sep 1, 2018 · 0 comments · Fixed by #338
Closed

Bug report for radix sort #336

InnoFang opened this issue Sep 1, 2018 · 0 comments · Fixed by #338

Comments

@InnoFang
Copy link
Contributor

InnoFang commented Sep 1, 2018

Description

if the test case for radix_sort.py is [104, 203, 308, 401], the result would be [401, 203, 104, 308]

It's wrong!

The reason is that if the tmp is always 0 in one loop, it will exit the loop. In other words, If the same digit of all numbers is 0, then the result may be wrong. The similar example like:
Input: [2018, 33017, 24016]
Output: [24016, 33017, 2018]
Wrong again!!

Suggestion

Do not use maxLength as a loop variable because the value of maxLength is related to tmp.

I think that by finding the maximum value of the array and assigning it to max_digit, using another variable digit with an initial value of 1 as the loop variable, each loop digit is multiplied by 10, and exit the loops when the digit greater than max_digit, which can guarantee the correct number of loops.

And the complexity will be O(nk + n) . n is the size of input list and k is the digit length of the number.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant