counting sort Archives

カウントソート–カウントソートアルゴリズム。に関しては？はい！そのとおりです!

アルゴリズムには少なくとも 2 つの配列が含まれます。最初の配列は –ソートする整数のリスト、2 番目 –サイズ = (最大数 – 最小数) + 1 の配列。最初はゼロのみを含みます。次に、最初の配列から数値が並べ替えられ、その数値要素を使用して 2 番目の配列のインデックスが取得され、1 ずつ増分されます。リスト全体を調べた後、最初の配列からの数値の繰り返し数を含む、完全に満たされた 2 番目の配列が得られます。アルゴリズムには重大なオーバーヘッドがあります – 2 番目の配列には、最初のリストにない数値のゼロも含まれます。メモリによるオーバーヘッド

2 番目の配列を受け取った後、それを反復処理し、インデックスでソートされた数値を書き込み、カウンターを 0 にデクリメントします。最初は、ゼロカウンタは無視されます。

カウントソートアルゴリズムの最適化されていない操作の例:

<オル>

入力配列 1,9,1,4,6,4,4

カウントする配列は 0,1,2,3,4,5,6,7,8,9 になります (最小値は 0、最大値は 9)

合計カウンタが 0,2,0,0,3,0,1,0,0,1 の場合

ソートされた配列の合計 1,1,4,4,4,6,9

Python 3 のアルゴリズムコード:


numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)

Из-за использования двух массивов, временная сложность алгоритма O(n + k)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/countingSort

Источники

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

Tag Archives: counting sort

カウンティングソート

Ссылки

Источники