計数ソート,基数ソートってなんや（Python）

おはようございます。しいです

バケット法に調べてたら知らない単語”計数ソート”ってのが出てきたので調べたメモをまとめていきます。

https://qiita.com/drken/items/44c60118ab3703f7727f#8-%E8%A8%88%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88-%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%81%AF%E9%87%8D%E8%A6%81%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0

上のけんちょんさんの第８章にのってるやつね

計数ソート(Counting sort)

これは大学の授業で書いてたやつだった別の名をCounting sortともいうらしい。

最初に最大値Nの非負の配列をソートする場合を考える。そのときに書く数値の数を数えて並べなおしソートするというものである。

  N =  int(input())#配列の大きさを取得
  A = list(map(int,input().split()))
  dp = [0]*(N+1)#辞書の用意
  ans = []#答えの配列
  for i in A:#出現した要素をカウント
      dp[i]+=1
  for e,i in enumerate(dp):#並び替え実行部分
      for j in range(i):#出現回数分追加してあげる
          ans.append(e)
  print(ans)

コメントのとおりだが最初に辞書を用意
Aの出現回数をカウント
出現回数分追加する

実質高速なのだが扱う整数の最大値に速度が依存するため注意

基数ソート

基数を決めて各桁ごとに比較していくと最終的にソートされるというもの

https://ko-gaku-jiji.hatenablog.jp/entry/2019/11/10/033214

詳しくはここ見たらイメージしやすいと思うよ

https://algoful.com/Archive/Algorithm/RadixSort

実装はここのCのやつを参考にします

    from collections import defaultdict
    from copy import copy
    D1 = defaultdict(list)
    N = int(input())
    A = list(map(int,input().split()))
    M = len(str(max(A))) #最大桁数の取得
    ans = []
    print(M)
    for i in range(M+1):
        if i == 0:
            for j in A:
                D1[j%10].append(j)
        else:
            for I in range(10):
                for j in tmpD[I]:
                    D1[(j%10**(i+1))//(10**(i))].append(j)
                    if i == M-1:ans.append(j)
        print(i,D1)      
        tmpD = copy(D1)
        D1 = defaultdict(list)
    ans = D1[0]
    print(ans)

defaultdict つかって作成

一番の肝は最初は１のけた使ってやるためうまいことソートされることじゃないかな

任意の桁取り出すのが少し物騒な実装になってるのが反省

    from collections import defaultdict
    from copy import copy
    D1 = defaultdict(list)
    N = int(input())
    A = list(map(int,input().split()))
    M = len(str(max(A))) #最大桁数の取得
    ans = []
    print(M)
    for i in range(M+1):
        if i == 0:
            for j in A:
                D1[j%10].append(j)
        else:
            for I in range(10):
                for j in tmpD[I]:
                    D1[(j//10**(i+1))%10].append(j)
                    if i == M-1:ans.append(j)
        print(i,D1)      
        tmpD = copy(D1)
        D1 = defaultdict(list)
    ans = D1[0]
    print(ans)

こっちのほうがわかりやすいね。

10**（取り出したい桁数−１）でわって10で割ったあまりをもとめる。

それじゃお昼ご飯食べてきます。