負数で動作するCountingSortを実装するにはどうすればよいですか？

Question

私はPythonでCounting Sortアルゴリズムを実装していますが、負の数を含む配列では機能しません。誰か助けてくれますか？

def counting(nlist): 
    nlist = list(nlist) 
    size = len(nlist) 

    if size < 2: 
     return nlist 

    k = max(nlist) 

    counter = [0] * (k + 1) 

    for i in nlist: 
     counter[i] += 1 

    ndx = 0; 
    for i in range(len(counter)): 
     while 0 < counter[i]: 
      nlist[ndx] = i 
      ndx += 1 
      counter[i] -= 1 

    return nlist 

Answer 1

単純なアプローチは、最小値がcounterの配列インデックス0に格納されているように、最小値を検索し、その分、あなたのインデックスを相殺するだけであろう。次に、あなたのwhileループで元の値を取得するために、背面の最小値を追加します。

m = min(nlist) 
k = max(nlist) - m 

counter = [0] * (k + 1) 

for i in nlist: 
    counter[i-m] += 1 

ndx = 0; 
for i in range(len(counter)): 
    while 0 < counter[i]: 
     nlist[ndx] = i+m 
     ndx += 1 
     counter[i] -= 1 

Answer 2

あなたはあなたの入力で最低値を検索し、あなたのインデックスにすべての方法をそのを追加することができ、ときにそれをバックに変換ビルドは、出力：

def counting(nlist): 
    nlist = list(nlist) 
    size = len(nlist) 

    if size < 2: 
     return nlist 

    low = min(nlist) 
    k = max(nlist) - low 

    counter = [0] * (k + 1) 

    for i in nlist: 
     counter[i - low] += 1 

    print(counter) # see what the counter list looks like. Remove in final version 
    ndx = 0; 
    for i in range(len(counter)): 
     while 0 < counter[i]: 
      nlist[ndx] = i + low 
      ndx += 1 
      counter[i] -= 1 

    return nlist