1. 키 비교 하지 않는 정렬 알고리즘

• 버블, 퀵 정렬들과 같이 키값을 비교해 정렬하지 않고 다른 방식으로 정렬하는 알고리즘
• 대표적으로 counting 정렬과 radix 정렬이 있다

2. Radix 정렬

원소의 각 자릿수에 대해 counting 정렬을 반복해 정렬하는 알고리즘

알고리즘

Algorithm countingSort(arr, exp):
    n = len(arr)
    base = 10
    sorted_arr = [0] * (n)
    count_arr = [0] * (base)
 
    # count
    for i in range(0, n):
        index = (arr[i] / exp)
        count_arr[int(index % base)] += 1
 
    # accumulated count
    for i in range(1, base):
        count_arr[i] += count_arr[i-1]
 
    # sort
    for i in range(n-1, 0, -1):
        index = (arr[i] / exp)
        sorted_arr[count_arr[int(index % base)] - 1] = arr[i]
        count_arr[int(index % base)] -= 1
         
    arr = sorted_arr
    
Algorithm radixSort(arr):
    # 최대값을 찾아 최대 자릿수로 사용한다
    max_value = max(arr)
    exp = 1
    while max_value/exp > 0:
        countingSort(arr, exp)
        exp *= 10

시간복잡도 (d=최대 자리 개수, r=진수, n=원소 개수) : O(d(n+r))

3. Counting 정렬

숫자의 빈도수를 측정해 정렬하는 알고리즘

A : 원래 배열
C : A 배열의 키값을 인덱스로 하여 빈도수 측정한 배열
S : C 배열을 축적값으로 바꾸고, 키값-1 인덱스에 인덱스값 삽입하여 정렬

알고리즘

def countingSort(arr):
    n = len(arr)
    max_value = max(arr)
    count_arr = [0] * (max_value+1)
    sorted_arr = [0] * (n)
    
    # count
    for num in arr:                    
        count_arr[num] += 1
        
    # accumulate count  
    for i in range(1, max_value+1):    
        count_arr[i] += count_arr[i-1]
        
    # sort
    for j in range(n-1, -1, -1):        
        sorted_arr[count_arr[arr[j]]-1] = arr[j]
        count_arr[arr[j]] -= 1
        
    return sorted_arr

시간복잡도 (k=최대키값) : O(n+k)
공간복잡도 (정렬된 배열) : O(n), (빈도수 배열) : O(k)