Skip to content

Instantly share code, notes, and snippets.

@MartinThoma
Created May 16, 2012 20:36
Show Gist options
  • Save MartinThoma/2713744 to your computer and use it in GitHub Desktop.
Save MartinThoma/2713744 to your computer and use it in GitHub Desktop.
Counting Sort implemenatation
#!/usr/bin/python
# -*- coding: utf-8 -*-
def countingSort(A, k):
"""
Implementation of counting sort.
@param A: the list of integers which should get sorted.
No element should be smaller than 1
@param k: the highest number in A
"""
# Create empty list for the sorted list
B = [0 for el in A]
# Initialise counter with zeroes
C = [0 for el in xrange(0, k+1)]
# Count elements
for i in xrange(0, len(A)):
C[A[i]] += 1
# How many elements are equal or lower?
for i in xrange(1, k + 1):
C[i] += C[i - 1]
# The actual sorting
for j in xrange(len(A)-1, 0 - 1, -1):
tmp = A[j]
tmp2= C[tmp] -1
B[tmp2] = tmp
C[tmp] -= 1
return B
""" Usage example """
print countingSort([6,0,2,0,1,3,4,6,1,3,2], 6)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment