Python implementation · Counting Sort of the top ten sorting algorithms

Posted May 26, 20202 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

  1. Apply for additional space based on the difference between the largest and smallest elements in the set to be sorted;
  2. Traverse the set to be sorted, and record the number of occurrences of each element in the extra space corresponding to the element value;
  3. Calculate the data in the extra space to get the correct position of each element;
  4. 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

Counting Sort Animation 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

Follow.png