Skip to content
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

bug report for radix sort #395

Closed
InnoFang opened this issue Sep 1, 2018 · 1 comment
Closed

bug report for radix sort #395

InnoFang opened this issue Sep 1, 2018 · 1 comment

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 digit_number 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 is_done as a loop variable because the value of is_done is related to digit_number.

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.

@InnoFang InnoFang mentioned this issue Sep 3, 2018
8 tasks
keon pushed a commit that referenced this issue Sep 4, 2018
* fix sort/radix_sort (#395)

* Add a new line for radix_sort.py
@InnoFang
Copy link
Contributor Author

InnoFang commented Sep 4, 2018

This issue had been solved, see #397

@InnoFang InnoFang closed this as completed Sep 4, 2018
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

No branches or pull requests

1 participant