April 3rd, 2013, 05:20 PM

Python Counting Sort
I have an assignment for class using counting sort for numbers between 099.
The program is supposed to start off like this...
Code:
def countingsort(alist):
counts=[]
for i in range(100):
counts.append(0)
#TODO: enter your implementation
#Test cases:
print(countingsort([2,16,77,65, 99, 4, 2, 16, 16]))
#expected [2,2,4,16,16,16,65,77,99]
However, I came up with code that looks like this (and it does work):
Code:
def countingsort(alist):
maximum = max(alist)
minimum = min(alist)
counting_alist = [0]*(maximumminimum+1)
for i in alist:
counting_alist[iminimum] += 1
sorted_alist = []
for i in range(minimum, maximum+1):
if counting_alist[iminimum] > 0:
for j in range(0, counting_alist[iminimum]):
sorted_alist.append(i)
return sorted_alist
print(countingsort([2,16,77,65, 99, 4, 2, 16, 16]))
Can anybody help me to get this program to look more like how my professor wants it?
April 3rd, 2013, 06:24 PM

Something's fishy, and I conclude that you didn't write the counting sort program you show. If you had written the program you'd know how to modify it to start
Code:
def countingsort(alist):
counts=[]
for i in range(100):
counts.append(0)
#TODO: enter your implementation
So, um, make an effort to do your homework then come back with a specific question.
And, so as not to come across as a total pisspot, try these experiments in your python interpreter:
Code:
>>> a = [2,16,77,65, 99, 4, 2, 16, 16]
>>> print(max(a))
>>> print(min(a))
>>> print(len(a))
>>> print('abc'*5)
>>> print([0]*3)
[code]
Code tags[/code] are essential for python code and Makefiles!
April 4th, 2013, 01:47 PM

Hey, thanks for the tough love.. My partner and I came up with this... Thoughts?
Big O needs to be O(n) and I believe this satisfies that.
Code:
def countingsort(alist):
counts = []
for i in range(100):
counts.append(0)
for i in alist:
counts[i] += 1
sortedList = []
for i in range(100):
if counts[i] > 0:
for j in range(counts[i]):
sortedList.append(i)
return sortedList
#Test cases:
print(countingsort([2,16,77,65, 99, 4, 2, 16, 16]))
#expected [2,2,4,16,16,16,65,77,99]
April 4th, 2013, 02:06 PM

Looks like a counting sort to me. You don't need the "if" statement, because
for j in range(0):
won't evaluate the block.
Code:
def countingsort(alist):
counts = []
for i in range(100):
counts.append(0)
for i in alist:
counts[i] += 1
sortedList = []
for i in range(100):
for j in range(counts[i]):
sortedList.append(i)
return sortedList
#Test cases:
print(countingsort([2,16,77,65, 99, 4, 2, 16, 16]))
#expected [2,2,4,16,16,16,65,77,99]
[code]
Code tags[/code] are essential for python code and Makefiles!
April 4th, 2013, 02:16 PM

Cool.. that will definitely make this O(n)...
Thanks for your help.