음수로 작동하는 CountingSort를 구현하려면 어떻게해야합니까?

Question

파이썬에서 다음과 같은 계산 정렬 알고리즘을 구현했지만 음수가 포함 된 배열에서는 작동하지 않습니다. 누군가 나를 도울 수 있습니까?

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