Variation of the counting sort algorithm?

Question

I realize this isn't the standard counting sort as stated in CLRS, but what does my simplified version lack that the standard counting sort has? I realize mine only sorts positive integers, but that should be pretty easy to tweak (by using maps).

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

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

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

    return sorted_array

array = [3,2,-1,1,5,0,10,18,25,25]
print array
print count_sort(array)

Edit: The reason why I thought this wasn't the standard counting sort was because the algorithm covered in the MIT OpenCourseware lecture seemed slightly more involved (http://youtu.be/0VqawRl3Xzs?t=34m54s).

What makes you think this isn't counting sort? This looks perfectly valid to me. — templatetypedef, Feb 14 '12 at 08:56
Yeah, I don't see a problem either. FWIW, you shouldn't even need maps to handle negative numbers - just create a big enough `count_array` to hold them all, and let the negative indices wrap around. — Nick Barnes, Feb 14 '12 at 09:42
There's a particular reason for not using the built-in `max()`? — Rik Poggi, Feb 14 '12 at 09:48
Thanks for the answer guys. See my edit above for why I thought this wasn't the standard counting sort. @RikPoggi - I'm new to Python; max(array) seems much better, thanks! I've tweaked the original code. — Zubair Khan, Feb 14 '12 at 10:08
This answer has a pythonic way of removing your inner for loop (see how result is extended: http://stackoverflow.com/questions/8775963/what-is-an-on-algorithm-to-pair-two-equally-lengthed-lists-in-order-in-place/8776258#8776258 — Rusty Rob, Feb 14 '12 at 10:30

score 2 · Answer 1 · answered Feb 14 '12 at 10:24

You're doing something odd with your min and max. Try this:

def count_sort(array):
    maximum = max(array)
    minimum = min(array)
    count_array = [0]*(maximum-minimum+1)

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

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

    print sorted_array

array = [3,2,-1,1,5,0,10,18,25,25]
print array
count_sort(array)

score 0 · Answer 2 · edited May 23 '17 at 11:44

I don't see problems with the way you're count-sorting, anyway some suggestions to your code come to mind that maybe can interest you.

For example the line:

minimum = min(0, min(array))

could be replaced with:

minimum = min(0, *array)

If you ran your code in python-2.x use xrange() instead of range(), so you could change:

for i in range(minimum, maximum+1):

with:

for i in xrange(minimum, maximum+1):

For the last loop you don't actually need range() at all, check out the question pythonic way to do something N times, so you could change:

for j in range(0, count_array[i]):
    sorted_array.append(i)

with:

for _ in itertools.repeat(None, count_array[i]):
    sorted_array.append(i)

score -1 · Answer 3 · answered Feb 14 '12 at 09:37

-1

Do you mean http://en.wikipedia.org/wiki/Counting_sort ?

If yes, it's almost similar to your code. But it has one improvement: "The relative order of items with equal keys is preserved here, i.e. this is a stable sort.". So if you are sorting key-value dictionary order of the values will remain the same if they have equal keys.

answered Feb 14 '12 at 09:37

Archeg

8,364
7
43
90

No, it is not stable. The created array does not contain copies of the initial elements but it is created using the `i` index. – Kru Feb 14 '12 at 09:43
Can you explain? That phrase in the quotes was simply copied from the wiki. I suppose the author meant that stable sort is the sort that preserves order in items with equal keys. Maybe that word isn't used well here, but anyway it's clear from the sentence before it, what does it mean – Archeg Feb 14 '12 at 10:03
Well, in the algorithm above the integers are sorted. On wikipedia, items linked to keys are. – Kru Feb 14 '12 at 11:00
1

Yep, when you are sorting just integers it doesn't matter. But in general when you are talking about sort problem it means that all integers could be used as a keys, so you need to sort the data with keys, but not the keys alone. The sorting algorithms in real life are used mostly to sort dictionaries, not just lists. Also you can what read what means stability (http://en.wikipedia.org/wiki/Sorting_algorithm#Stability) in the sorting algorithms. Sorry for providing wiki links, if you think that wiki isn't truthly enough - you can view links in the bottom of the wiki page. – Archeg Feb 14 '12 at 11:11

Variation of the counting sort algorithm?

3 Answers3