계수정렬 음수포함 (counting sort with negative numbers) - 파이썬(python)

음수포함된 리스트 정렬하는 계수정렬 (안정정렬)

 

def counting_sort_negative(lists):
   
    if len(lists)<=1:
        return lists

    pos_max=max(lists)
    neg_max=abs(min(lists))

    pos_t=[0 for _ in range(pos_max+1)]
    neg_t=[0 for _ in range(neg_max+1)]

    for i in lists:
        if i>=0:
            pos_t[i]+=1
        else:
            neg_t[-i]+=1

    for j in range(1,len(pos_t)):
        pos_t[j]+=pos_t[j-1]

    for k in range(1,len(neg_t)):
        neg_t[k]+=neg_t[k-1]
   
    if len(pos_t)==0:
        result_pos=[]
    else:
        result_pos=[0]*pos_t[-1]
    if len(neg_t)==0:
        result_neg=[]
    else:
        result_neg=[0]*neg_t[-1]

    #loop reverse lists and sort
    # two part / pos and neg
    for m in reversed(lists):
        if m>=0:
            result_pos[pos_t[m]-1]=m
            pos_t[m]-=1
        else:
            result_neg[neg_t[-m]-1]=m
            neg_t[-m]-=1

    result=result_neg[::-1]+result_pos
    return result