#
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. **************************************************************************/ public class SinglyLinkedList { Node head = null; Node tail = null; /************************************************************************ * 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/java/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. ************************************************************************/ public void countingSort(int max) { //create a bucket for each key int A[] = new int[max + 1];//Java initializes int arrays to 0. //count recurrence of keys for (Node t = head; null != t; t = t.next) { A[t.data]++; } //swap sorted data back into LinkedList Node t = head; for (int i = 0; i < A.length; i++) { for (int x = 0; x < A[i]; x++) { t.data = i; t = t.next; } } } }

public class SinglyLinkedListTest { /** * Test of countingSort method, of class SinglyLinkedList. */ @Test public void testCountingSort() { System.out.println("countingSort"); int[] input = {9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11}; SinglyLinkedList linkedList = new SinglyLinkedList(); for (int i = 0; i < input.length; i++) { linkedList.addToTail(input[i]); } assertTrue(Arrays.equals(input, linkedList.toArray())); Arrays.sort(input); assertFalse(Arrays.equals(input, linkedList.toArray())); linkedList.countingSort(19); assertTrue(Arrays.equals(input, linkedList.toArray())); } }