### Thread: Python Counting Sort

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
15
Rep Power
0

#### Python Counting Sort

I have an assignment for class using counting sort for numbers between 0-99.

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]*(maximum-minimum+1)

for i in alist:
counting_alist[i-minimum] += 1

sorted_alist = []
for i in range(minimum, maximum+1):
if counting_alist[i-minimum] > 0:
for j in range(0, counting_alist[i-minimum]):
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?
2. 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)```
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
15
Rep Power
0
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]```
4. 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]```
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
15
Rep Power
0
Cool.. that will definitely make this O(n)...

Thanks for your help.