#1
  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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,995
    Rep Power
    481
    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!
  4. #3
  5. 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]
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,995
    Rep Power
    481
    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!
  8. #5
  9. 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.

IMN logo majestic logo threadwatch logo seochat tools logo