Pythonアルゴリズム-カウントソート

カウントソート

1.アルゴリズム紹介

2.アルゴリズム思想

3.アルゴリズムプロセス

4.pythonコード実装

コード1

最適化後のコード3

1.アルゴリズムの紹介

カウントソートは、空間的複雑度および時間的複雑度がいずれもO(n+k)であり、kは整数の範囲である比較に基づいていないソートアルゴリズムである.比較に基づく並べ替えアルゴリズムの時間的複雑さの最小化はO(nlogn)であった.

カウントソートの核心は、入力されたデータ値をキーに変換して追加のオープン配列空間に格納することである.線形時間複雑度のソートとして、カウントソートでは、入力されたデータが確定範囲の整数である必要があります.

カウントソートは、データ範囲の広い配列に対して、多くの時間とメモリを必要とします.

2.アルゴリズム思想
ソートする配列をA={1,0,3,1,0,1,1}とし、ここで最大値は3、最小値は0とすると、長さは3+1-0=4の配列Cを作成します.次に配列Aを1回走査し、A中の各要素の総数を求め、配列Cの対応ユニットに保持する.例えば0の出現回数が2回であれば、C[0]=2である.1の出現回数が4回であればC[1]=4となる.C=[2,4,0,1]CはAの要素を下にしているので、このようにすると、Aの要素はCの中で自然に秩序化され、その後、0,1,2,3より小さい要素の個数、例えば1より小さい(1を含む)要素は6つ統計される.C,C=[2,6,6,7]を更新し,Cを更新するのはソートの安定性を保証するためである.そして、このCにおけるレコードを各要素のカウントで出力配列Bに展開し、ソートが完了する.すなわち、B[0]からB[1]までが0であり、B[2]からB[5]までが1である.
3.アルゴリズムプロセス

は、まず配列の最大値を探し出す.配列のすべての値は0から最大値の間にあるに違いない.例えば、配列の範囲が0-10の場合、配列の値は0-10の11の数の間にあるに違いない.

要素がすべて0の配列を確立し、配列の下に0から最大値と表記し、最大値=10と仮定すると、下図のように

要素
0
0
0
0
0
0
0
0
0
0
0
要素の下付き
0
1
2
3
4
5
6
7
8
9
10
例を挙げて説明する

まず20個のランダム整数の値を仮定すると、2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,10,9,10,10はまずこの無秩序なランダム配列を遍歴し、各要素はその値に従って番号を座席に入れ、配列の下付き要素を+1操作し、例えば、最初の要素が2であれば、下付き2の要素に1:

を加える.
要素
0
0
1
0
0
0
0
0
0
0
0
要素の下付き
0
1
2
3
4
5
6
7
8
9
10
2番目の要素が4の場合、下に4と表示されている要素に1を加えます.
要素
0
0
1
0
1
0
0
0
0
0
0
要素の下付き
0
1
2
3
4
5
6
7
8
9
10
3番目の要素が2の場合、下の2の要素に1を加えます.
要素
0
0
2
0
1
0
0
0
0
0
0
要素の下付き
0
1
2
3
4
5
6
7
8
9
10
このように元の配列を巡回し、最終的な結果:
要素
3
2
2
1
2
2
1
2
1
2
2
要素の下付き
0
1
2
3
4
5
6
7
8
9
10
これにより、配列内の各値の出現回数を統計し、この統計結果があれば配列を直接遍歴することができ、配列要素の下付き値を出力し、要素の値は数で、何回出力することができる.
4.pythonコード実装
コード1

def count_sort1(arr):
    maxi = max(arr)  #      
    count_arr = [0 for _ in range(maxi + 1)]  #      0  
    #               
    for value in arr:
        count_arr[value] += 1
    arr.clear()  #       
    for index, element in enumerate(count_arr):  # index:    
        for i in range(element):
            arr.append(index)  


def count_sort2(arr):
    maxi = max(arr)   #          
    count_arr = [0 for _ in range(maxi + 1)]  #      0  
    #               
    for value in arr:
        count_arr[value] += 1

    new_arr = []  #        
    for i in range(len(count_arr)):
        while count_arr[i] != 0:
            new_arr.append(i)
            count_arr[i] -= 1
    return new_arr       


import random
numbers = [random.randint(0, 10)   for _ in range(20)]
print(numbers)
count_sort1(numbers)
print(numbers)
numbers2=[3,4,5,6,9,5,2,1,2,3,6,8,9,7]
print(count_sort2(numbers2))

コードのいくつかの解釈

enumerate()関数の使用方法:enumerate()関数は、リスト、メタグループ、文字列などの遍歴可能なデータオブジェクトをインデックスシーケンスに結合するために使用され、データとデータの下付き文字をリストします.一般的にforループで使用されます.構文フォーマット:enumerate(sequence,[start=0])パラメータの説明:1.sequence:シーケンス、反復器、または反復をサポートする他のオブジェクト2.start:下付き開始位置

は、enumerateを使用すると、

という結果を得るsequenceが存在することを例示する.

1  start        sequence[0]
2  start+1　 　　sequence[1]
3  start+2      sequence[2]
...

例:

seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
    print(i, element）


    ：
0    one
1    two
2    three

この関数は、下の要素値と対応する下付きインデックスを出力します.

for _ in range(maxi+1)の使い方:

list1 = [0  for _ in range(10)]
print(list)
list2=[2**2  for _ in range(5)]
print(list2)

出力結果:

list1: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
list2:[2, 2, 2, 2, 2]

ここの下線()プレースホルダで、中身にかかわらず、前の内容を何度もループさせる役割を果たしています.つまりfor_In range(n)の役割は,単にn回のサイクルを繰り返すことである.

random.randint(0,10):10

を除く0-10の間の数をランダムに返します.
最適化されたコード3
上のコードは最初から数列の最大値maxiを求め、作成した配列count_arrは、配列の最後の下付きラベルがmaxiであることを保証するためにmaxi+1の長さである.しかし、このコードは厳密ではありません.配列の最小値が50で、最大値が59であれば、上のコードに従って長さが60の配列を作成する必要があります.前の50の数(0-49)はありません.それでは空間を浪費します.だから、配列の長さは、最大値-最小値+1で、配列の最小値をオフセット量とします.例:配列が55,54,59,50,51,52,51,53,56,55の場合、オフセット量=最小値(50)となり、第1の数55の場合、対応する配列の下付きは55-50=5であるべきである
順序付けを安定させるためには、**[50,51,52,...,59]より小さい要素個数、例えば51より小さい要素個数(51を含む)の3つの元のカウント配列を順次統計することができる.
要素の数
1
2
1
1
1
2
1
0
0
1
オフセット後の下付き
0
1
2
3
4
5
6
7
8
9
要素の下付き
50
51
52
53
54
55
56
57
58
59
加算されたカウント配列は
加算の原則は、各要素の出現回数=その前のすべての要素の出現回数+その要素の出現回数
加算回数
1
3
4
5
6
8
9
9
9
10
オフセット後の下付き
0
1
2
3
4
5
6
7
8
9
要素の下付き
50
51
52
53
54
55
56
57
58
59
加算されたカウント配列要素の値は、要素の位置に等しくなります.たとえば、下付き6の要素値は9で、元の数列を表す値56の最終的なソートは、9番目に最適化されたコードです.

def count_sort2(arr):
    maxi = max(arr)
    mini = min(arr)
    count_arr_length = maxi - mini + 1  #               ， 4-9 9+1-4=6  
    count_arr = [0 for _ in range(count_arr_length)]   #       0   

    for value in arr:
        count_arr[value - mini] += 1   #              

    #  count_arr[i]  <=i     ，                    
    for i in range(1, count_arr_length):
        count_arr[i] = count_arr[i] + count_arr[i - 1]

    new_arr = [0 for _ in range(len(arr))]   #       
    for i in range(len(arr)-1, -1, -1):    #               
        new_arr[count_arr[arr[i] - mini] - 1] = arr[i]   # -1       0   
        count_arr[arr[i] - mini] -= 1   #        ，      
    return new_arr


if __name__ == '__main__':
    user_input = input('       ， \",\"  :
').strip()
    #strip()                 （     ）
    unsorted = [int(item) for item in user_input.split(',')]
    print(count_sort2(unsorted))
    

ここで私が言った比較はあまり分かりにくいかもしれませんが、カウントソートの詳細については、ここをクリックして確認してください.
カウント・ソートは、最大値と最小値の差が大きくないリストに適用されます.リストの最小値が1で、最大値が1億であれば、カウント・ソートには1億+1の長さのリストを開く必要があります.時間がかかります.