10
\$\begingroup\$

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:]
\$\endgroup\$
  • \$\begingroup\$ Are you using Python 2 or 3? \$\endgroup\$ – Phrancis Dec 6 '16 at 9:07
  • \$\begingroup\$ I am using Python 2.7.11 \$\endgroup\$ – user3837690 Dec 6 '16 at 18:11
10
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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]) \$\endgroup\$ – ChatterOne Dec 6 '16 at 9:27
  • \$\begingroup\$ @ChatterOne good idea! I'll add this as a side-note in my answer ^^ \$\endgroup\$ – Grajdeanu Alex. Dec 6 '16 at 9:30
  • \$\begingroup\$ 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. \$\endgroup\$ – user3837690 Dec 6 '16 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.