Oct 6, 2019
diff --git a/allalgorithms/sorting/__init__.py b/allalgorithms/sorting/__init__.py
 from .cocktail_shaker_sort import cocktail_shaker_sort
 from .tree_sort import tree_sort
 from .heap_sort import heap_sort
 from .counting_sort import counting_sort
diff --git a/allalgorithms/sorting/counting_sort.py b/allalgorithms/sorting/counting_sort.py
 # -*- coding: UTF-8 -*-
 #
 # Radix Sort Algorithm
 # The All ▲lgorithms library for python
 #
 # Contributed by: Nicholas Gao
 # Github: @n-gao
 #
 class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def add_child(self, value):
        if value < self.value:
            if self.left_child is None:
                self.left_child = BinaryTree(value)
            else:
                self.left_child.add_child(value)
        else:
            if self.right_child is None:
                self.right_child = BinaryTree(value)
            else:
                self.right_child.add_child(value)

    def get_sorted_values(self):
        result = []
        if self.left_child is not None:
            result = self.left_child.get_sorted_values()
        result.append(self.value)
        if self.right_child is not None:
            result = result + self.right_child.get_sorted_values()
        return result

 def counting_sort(arr):
    counts = {}
    tree = None
    for value in arr:
        if value in counts:
            counts[value] += 1
        else:
            counts[value] = counts[value] + 1 if value in counts else 1
            if tree is None:
                tree = BinaryTree(value)
            else:
                tree.add_child(value)

    sorted_values = tree.get_sorted_values()
    i = 0
    for value in sorted_values:
        for _ in range(counts[value]):
            arr[i] = value
            i += 1

    return arr
diff --git a/docs/sorting/counting-sort.md b/docs/sorting/counting-sort.md
 # Counting sort
 Counting sort is a sorting algorithm which does not actually sort
 the array but rather reconstructs it. It operates by counting how
 often every unique item (e.g., a certain number) occurs, sorts the
 unique items by TreeSort and then reconstructs an array by copying
 every unique item (the number of occurences)th times into the result.
 Its advantage is the fast computation which is only linear with respect
 of the input array *if* the number of unique items is significantly
 smaller than the number of items.

 ## Install

 ```
 pip install allalgorithms
 ```

 ## Usage

 ```py
 from allalgorithms.sorting import counting_sort

 arr = [77, 2, 10, -2, 1, 7]

 print(counting_sort(arr))
 # -> [-2, 1, 2, 7, 10, 77]
 ```

 ## API

 ```
 counting_sort(array)
 ```

 > Returns a sorted array (does in-place replacements)

 ##### Params:

 - `array`: Array to sort

diff --git a/tests/test_sorting.py b/tests/test_sorting.py
    tree_sort,
    heap_sort,
    shell_sort,
    counting_sort
 )


    def test_tree_sort(self):
        self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))

    def test_counting_sort(self):
        self.assertEqual([-44, 1, 2, 3, 7, 19], counting_sort([7, 3, 2, 19, -44, 1]))

    def test_heap_sort(self):
        array = [7, 3, 2, 19, -44, 1]
        heap_sort(array)
Original file line number	Diff line number	Diff line change
Expand Up		@@ -7,3 +7,4 @@
		from .cocktail_shaker_sort import cocktail_shaker_sort
		from .tree_sort import tree_sort
		from .heap_sort import heap_sort
		from .counting_sort import counting_sort
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,56 @@
		# -- coding: UTF-8 --
		#
		# Radix Sort Algorithm
		# The All ▲lgorithms library for python
		#
		# Contributed by: Nicholas Gao
		# Github: @n-gao
		#
		class BinaryTree:
		def __init__(self, value):
		self.value = value
		self.left_child = None
		self.right_child = None

		def add_child(self, value):
		if value < self.value:
		if self.left_child is None:
		self.left_child = BinaryTree(value)
		else:
		self.left_child.add_child(value)
		else:
		if self.right_child is None:
		self.right_child = BinaryTree(value)
		else:
		self.right_child.add_child(value)

		def get_sorted_values(self):
		result = []
		if self.left_child is not None:
		result = self.left_child.get_sorted_values()
		result.append(self.value)
		if self.right_child is not None:
		result = result + self.right_child.get_sorted_values()
		return result

		def counting_sort(arr):
		counts = {}
		tree = None
		for value in arr:
		if value in counts:
		counts[value] += 1
		else:
		counts[value] = counts[value] + 1 if value in counts else 1
		if tree is None:
		tree = BinaryTree(value)
		else:
		tree.add_child(value)

		sorted_values = tree.get_sorted_values()
		i = 0
		for value in sorted_values:
		for _ in range(counts[value]):
		arr[i] = value
		i += 1

		return arr
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,39 @@
		# Counting sort
		Counting sort is a sorting algorithm which does not actually sort
		the array but rather reconstructs it. It operates by counting how
		often every unique item (e.g., a certain number) occurs, sorts the
		unique items by TreeSort and then reconstructs an array by copying
		every unique item (the number of occurences)th times into the result.
		Its advantage is the fast computation which is only linear with respect
		of the input array if the number of unique items is significantly
		smaller than the number of items.

		## Install

		```
		pip install allalgorithms
		```

		## Usage

		```py
		from allalgorithms.sorting import counting_sort

		arr = [77, 2, 10, -2, 1, 7]

		print(counting_sort(arr))
		# -> [-2, 1, 2, 7, 10, 77]
		```

		## API

		```
		counting_sort(array)
		```

		> Returns a sorted array (does in-place replacements)

		##### Params:

		- `array`: Array to sort
Original file line number	Diff line number	Diff line change
Expand Up		@@ -11,6 +11,7 @@
		tree_sort,
		heap_sort,
		shell_sort,
		counting_sort
		)


Expand DownExpand Up		@@ -39,6 +40,9 @@ def test_cocktail_shaker_sort(self):
		def test_tree_sort(self):
		self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))

		def test_counting_sort(self):
		self.assertEqual([-44, 1, 2, 3, 7, 19], counting_sort([7, 3, 2, 19, -44, 1]))

		def test_heap_sort(self):
		array = [7, 3, 2, 19, -44, 1]
		heap_sort(array)
Expand Down