Make this implementation of counting sort Pythonic

This is my crude attempt at implementing a counting sort algorithm. My goal is to be able to sort lists of ints, negative and positive. As you can see I've employed such hacks as return res[1:] to get by. I'd appreciate any feedback I can get to make this a more pythonic implementation.

def find_min(a_list):
min = a_list[0]
for item in a_list:
if item < min:
min = item
return min

def find_max(a_list):
max = a_list[0]
for item in a_list:
if item > max:
max = item
return max

def counting_sort(a_list):
min = find_min(a_list)
max = find_max(a_list)

counts = [0] * (abs(max) + abs(min) + 1)

for i in range(0, len(a_list), 1):
counts[a_list[i] - min] += 1

sum = 0
for j in range(0, len(counts), 1):
sum += counts[j]
counts[j] = sum

res = [0] * (len(a_list)+1)
for k in range(0, len(a_list), 1):
res_index = counts[a_list[k]-min]
res[res_index] = a_list[k]
counts[a_list[k]-min] -= 1

return res[1:]

• Are you using Python 2 or 3? – Phrancis Dec 6 '16 at 9:07
• I am using Python 2.7.11 – user3837690 Dec 6 '16 at 18:11

My two cents:

You can get rid of def find_min(a_list): and def find_max(a_list):. Instead, use python's built-ins min() and max():

min(iterable[, key])

Return the smallest item in an iterable or the smallest of two or more arguments.

If one positional argument is provided, iterable must be a non-empty iterable (such as a non-empty string, tuple or list). The smallest item in the iterable is returned. If two or more positional arguments are provided, the smallest of the positional arguments is returned.

max(iterable[, key])

Return the largest item in an iterable or the largest of two or more arguments.

If one positional argument is provided, iterable must be a non-empty iterable (such as a non-empty string, tuple or list). The largest item in the iterable is returned. If two or more positional arguments are provided, the largest of the positional arguments is returned.

So you'll have:

...
min_element, max_element = min(a_list), max(a_list)
...


Now, regarding you algorithm, you can avoid those hacks you were talking about by rewriting your function as:

def count_sort(array):
min_element, max_element = min(array), max(array)
count_array = [0] * (max_element - min_element + 1)

for val in array:
count_array[val - min_element] += 1

sorted_array = []
for i in range(min_element, max_element + 1):
if count_array[i - min_element] > 0:
for j in range(0, count_array[i - min_element]):
sorted_array.append(i)

return sorted_array


More, as @ChatterOne mentioned, instead of the final for loop with append, you could do:

sorted_array.extend([i] * count_array[i - min_element])


So, your final code would look like this:

def count_sort(array):
min_element, max_element = min(array), max(array)
count_array = [0] * (max_element - min_element + 1)

for val in array:
count_array[val - min_element] += 1

sorted_array = []
for i in range(min_element, max_element + 1):
if count_array[i - min_element] > 0:
for j in range(0, count_array[i - min_element]):
sorted_array.append(i)

return sorted_array

if __name__ == '__main__':
my_array = [3, 2, -1, 1, 5, 0, 10, 18, 25, 25]
print(count_sort(my_array))


or

def count_sort(array):
min_element, max_element = min(array), max(array)
count_array = [0] * (max_element - min_element + 1)

for val in array:
count_array[val - min_element] += 1

sorted_array = []
for i in range(min_element, max_element + 1):
if count_array[i - min_element] > 0:
sorted_array.extend([i] * count_array[i - min_element])

return sorted_array

if __name__ == '__main__':
my_array = [3, 2, -1, 1, 5, 0, 10, 18, 25, 25]
print(count_sort(my_array))


Extras:

You can see that I also added if __name__ == '__main__'. By doing the main check, you can have that code execute only when you want to run the module as a program, and not have it execute when someone just wants to import your module and call your functions themselves.

I also changed the names min and max(which are already built-ins in Python) to min_element and max_element, respectively.

And the result:

[-1, 0, 1, 2, 3, 5, 10, 18, 25, 25]

• There's not much of a difference, but it's probably worth mentioning that instead of the final for loop with append, you could do sorted_array.extend([i] * count_array[i - min_element]) – ChatterOne Dec 6 '16 at 9:27
• @ChatterOne good idea! I'll add this as a side-note in my answer ^^ – Grajdeanu Alex. Dec 6 '16 at 9:30
• Gents, thank you do much for the feedback. I should have mentioned that I purposely did not use the built in min and max functions in spirit of writing as much of it on my own as possible. – user3837690 Dec 6 '16 at 18:15