# counting sort

noneunknown

python

2 years ago

1.5 kB

3

Indexable

Never

^{}

def unstable_counting_sort(arr, size): max_key = max(arr) count_arr: List[int] = [0] * (max_key + 1) for key in arr: count_arr[key] += 1 cur_index: int = 0 for index, counter in enumerate(count_arr): for _ in range(counter): arr[cur_index] = index cur_index += 1 def stable_counting_sort(arr: List[int], size: int): max_key = max(arr) count_arr: List[int] = [0] * (max_key + 1) output: List[int] = [None] * size # 1) count each item appearance in original array # 2) map each item key to corresponding index in count_array for key in arr: count_arr[key] += 1 # for adding n item in a row you should now either lb or end index to do so # the following loop will make the count array to show end index of each item # by doing this you know the position of start adding item in output array for i in range(0, max_key): count_arr[i + 1] += count_arr[i] # for each key in original array find end index to replace it with # start from there untill you can not find anymore of that key in original array # this will make sorting stable because you place object in list by order # ... you find it in original array, so the order is not changed for i in range(size - 1, -1, -1): key = arr[i] count_arr[key] -= 1 output[count_arr[key]] = key # update given array for index, item in enumerate(output): arr[index] = item