#
Counting Sort

#======================================================================= # Author: Isai Damier # Title: Singly Linked List # Project: geekviewpoint # Package: datastructure # # Description: A LinkedList is a data structure that allows access # to a collection of data using pointers/references. While an # array can also be defined as above, LinkedLists and arrays differ # in how they are stored in memory and in the operations they # allow. Unlike an array that must be stored in a block of memory, # the nodes of a LinkedList can be stored anywhere because each # node has a reference to the node that succeeds it. Because the # nodes are stored so loosely, inserting nodes into a LinkedList # is easy; whereas in an array, all the succeeding elements must # be shifted. Of course, insertion also means changing the size of # the array, which means creating the entire array anew. # # Perhaps the greatest beauty of LinkedList is that it allows # accessing an entire sequence of nodes using only one variable: # a reference to the first node in the sequence. # # Countless operations can be performed on LinkedLists. Following # are a few, ranging from the common to the very interesting. #======================================================================= #===================================================================== # Time Complexity of Solution: # O(n*log n). # # Description: sort this LinkedList # # Technical Details: If the elements of this LinkedList fall within a # known short range, then it makes sense to use an integer algorithm # like counting sort (ref geekviewpoint/python/sorting/counting_sort), # since integer algorithms are very fast. # # To keep the implementation simple, assume the elements range from 0 # to max, inclusive. Counting sort then proceeds by creating a bucket # for each key; incrementing a counter each time a key recurs in the # list; then emptying the buckets back into the LinkedList. #******#============================================================== import collections class SinglyLinkedList( object ): def __init__( self ): self.head , self.tail = None, None def countingsort( self, k ): counter = [0] * ( k + 1 ) t = self.head while None != t: counter[t.data] += 1 t = t.next t = self.head for i in range( len( counter ) ): while 0 < counter[i]: t.data = i; t = t.next counter[i] -= 1 class Node( object ): def __init__( self, data, next = None ): self.data = data self.next = next

import unittest from algorithms.SinglyLinkedList import SinglyLinkedList import random class Test( unittest.TestCase ): #===================================================================== # Test of countingSort method, of class SinglyLinkedList. #===================================================================== def testCountingSort( self ): tape = [9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11] linkedList = SinglyLinkedList() for i in range( len( tape ) ): linkedList.addToTail( tape[i] ) self.assertEquals( tape, linkedList.toArray() ) tape.sort() self.assertNotEquals( tape, linkedList.toArray() ) linkedList.countingsort( 19 ) self.assertEquals( tape, linkedList.toArray() )