Python implementation · Counting Sort of the top ten sorting algorithms
Posted May 26, 2020 • 2 min read
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 = *(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]
Analysis of Algorithms
The data range is constant k, the number of elements to be sorted is n, and the total time complexity is $O(n + k) $.
Counting and sorting only requires an extra space complexity of $O(k) $, so the sorting and counting space complexity is $O(k) $.
Counting sorting does not change the relative position of equal elements, so counting sorting is stable.
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
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