# Python implementation · Counting Sort of the top ten sorting algorithms

Posted May 26, 2020 • 2 min read

## Introduction

Counting sorting(Counting Sort) is not a sorting algorithm based on comparison. Its core lies in converting the input data value into a key and storing it in an extra array space. As a sort of linear time complexity, count sorting requires that the input data must be an integer with a certain range. Its basic idea is:for each element x in a given input sequence, determine the number of elements in the sequence that are less than or equal to x, and then store x directly in the correct position of the final sort sequence.

## Algorithm implementation steps

- Apply for additional space based on the difference between the largest and smallest elements in the set to be sorted;
- Traverse the set to be sorted, and record the number of occurrences of each element in the extra space corresponding to the element value;
- Calculate the data in the extra space to get the correct position of each element;
- Move each element of the set to be sorted to the correct position calculated.

## Python code implementation

```
# counting_sort code implementation
from typing import List
def counting_sort(arr:List [int]):
max = min = 0
for i in arr:
if i <min:
min = i
if i> max:
max = i
count = [0]*(max-min +1)
for j in range(max-min + 1):
count [j]= 0
for index in arr:
count [index-min]+ = 1
index = 0
for a in range(max-min + 1):
for c in range(count [a]):
arr [index]= a + min
index + = 1
# Test Data
if __name__ == '__main__':
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("raw data:", arr)
counting_sort(arr)
print("Count sort results", arr)
# Output result
Original data:[17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
Counting and sorting results [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]
```

## Animated demo

## Analysis of Algorithms

time complexity

The data range is constant k, the number of elements to be sorted is n, and the total time complexity is $O(n + k) $.

Space complexity

Counting and sorting only requires an extra space complexity of $O(k) $, so the sorting and counting space complexity is $O(k) $.

Stability

Counting sorting does not change the relative position of equal elements, so counting sorting is stable.

Overview

Time complexity(average) Time complexity(best) Time complexity(worst) Space complexity Sort by Stability $O(n + k) $ $O(n + k) $ $O(n + k) $ $O(k) $ out-place stable

## contact us

Personal blog website: http://www.bling2.cn/

Github address: https://github.com/lb971216008/Use-Python-to-Achieve

Know the column: https://zhuanlan.zhihu.com/Use-Python-to-Achieve

Small column: https://xiaozhuanlan.com/Use-Python-to-Achieve

Blog Park: https://www.cnblogs.com/Use-Python-to-Achieve