Doubt in counting_sort algorithm #632
Unanswered
0xChaitanya
asked this question in
Q&A
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
see pydatastructs/linear_data_structures/algorithms.py
in line number 420, we are doing count[x-min_val] += 1 but should't it be count[x-min_val] -= 1?
Still, the algorithm runs bug-free, but in counting sort, we subtract the prefix sum by 1. and do not add 1, so I want to know how.
Also, in the final step of counting_sort, we should go from top to bottom rather than from bottom to top, i.e., range len(array) to 0. This thing preserves the relative order of elements in the array. The current implementation of counting_sort violates the relative order as it starts from the range 0 to len(array). Hence, making counting_sort a non-stable sorting algorithm.
Beta Was this translation helpful? Give feedback.
All reactions