[알고리즘] 분포기반 정렬

분포 기반 정렬

 규칙에 따라 입력된 배열 원소를 여러개의 중간 구조로 분산한 후 결과 배열에 배치하는 정렬 방식. 배열 내 값들 사이에서 비교가 발생하지 않는다는 특징이 있다. 

 보통 비교 기반 정렬의 시간 복잡도는 O(log n) 이하로 떨어질 수 없다고 알려져 있는데 비해 분포 기반의 정렬을 이용하면 해당 수치 이하로 정렬 시간을 줄일 수 있어 속도가 중요한 경우 사용을 고려할 수 있다. 다만 탐색 기반의 알고리즘에 비해 공간 복잡도가 높을 수 있으며, 입력이 일정한 범위 내에서 고르게 분포해야 좋은 성능을 보인다.

---

계수 정렬

 배열 내 특정 원소가 등장하는 횟수를 다른 공간에 저장해두고, 이를 누적 합 형식으로 변경하여 가진 후(Idx 배열), 배열을 탐색하면서 특정 원소가 등장할 때마다 Idx 배열을 기반으로 키 값의 위치를 설정하는 방식의 정렬 방법이다. 값은 맨 뒤 레코드부터 차례대로 배열에 삽입한다.

 배열 내부의 값은 반드시 일정 범위 내에 이산적으로 존재해야 한다.

코드

"""
일정한 범위 내의 값만으로 배열이 구성될 때 사용한다.
1. 각 원소의 갯수를 세서 대응되는 배열에 갯수 적어놓기
2. 갯수가 적힌 배열을 누적 형태로 바꿈 -> 이전 행의 값 더하기
3. 데이터 배열의 뒤에서부터 하나씩 숫자를 읽어 / 해당 값에 대응되는 갯수 적힌 배열 값에 해당하는 인덱스 위치에 넣음.
4. 값을 인덱스 위치에 넣은 후, 갯수 배열에 적힌 숫자를 1 감소시킨다.

현재 예시에서는 0~5 범위에 대해서 counting sort를 진행한다.
만약 여러 범위를 커버해야 한다면 가질 수 있는 값을 배열로 입력받고, set 자료구조에 값을 넣어두는 등 가능.

stop = 5 이면, 배열의 길이는 6.
여기서는 0 ~ n 숫자에 대한 계수 정렬을 나타낸다.
"""
def counting_sort(arr: list[int], stop: int):
    idx = [0 for _ in range(stop + 1)] # 특정 값이 등장한 횟수를 지정하는 배열
    result = [0 for _ in range(len(arr))] # 정렬된 결과가 저장되는 배열.
    # 갯수 세는 배열 초기화
    for i in arr :
        idx[i] += 1 # 배열 요소들에 대응되는 갯수 기록

    for i in range(1, len(idx)): # 누적 합 형태로 카운트 변경
        idx[i] += idx[i - 1]

    for i in range(len(idx)) :
        if idx[i] > 0 :
            idx[i] -= 1 # 인덱스를 맞춰주기 위해 1씩 값을 감소시킨다.

    arr.reverse() # 뒤에서부터 값을 하나씩 빼면서 특정 위치에 저장한다.
                    # 해당 동작을 위한 배열 뒤집기.

    for val in arr :
        result[idx[val]] = val
        idx[val] -= 1
    
    return result

arr = [5,3,4,1,5,4,1,4]
arr = counting_sort(arr,5)
print(arr)

# 시간 복잡도 : O(n + k) -> O(n)
# 제자리성 : 입력 크기에 비례하는 배열이 필요하므로, 제자리성 없음
# 안정성 : 배열의 뒤 값부터 순서대로 배치하므로, 순서 변경 없어 안정적임.

• 시간 복잡도 : O(n)
• 제자리성 : 입력된 배열 내 원소가 가질 수 있는 값의 범위에 해당하는 크기의 counting 배열이 필요하다.
• 안정성 : 뒤쪽 레코드에서부터 순서대로 값을 배치하므로, 안정적이다.

기수 정렬

 입력된 배열의 원소들에 대해 각 자리 (radix) 의 값에 따라 분류 및 결합하는 과정을 모든 radix에 대해 수행하면서 진행되는 정렬. 각 단계에서는 현재 자리(radix) 에 대한 정렬이 진행되므로, 순서가 변경되어서는 안된다. 

코드

"""
전체 키를 여러 자리로 나누어 각 자리마다 안정적 정렬을 적용한다.
왜 안정적 ? : 안정성이 없는 알고리즘 이용시, 이전 단계에 분류했던 것들이 섞일 수 있음!
따라서 안정성이 있는 알고리즘 (ex 삽입 정렬) 등을 각 단계에서 적용.
여기서는 정수에 대한 정렬을 수행해본다.
"""


def getDig(number: int, digit: int):
    return int(number/(10**digit)) % 10


def radix_sort_for_integer(arr: list[int]):
    result = arr.copy()
    can_exit = False

    digit = 0
    while not can_exit:
        radix = [[] for _ in range(10)]

        for val in result:
            dig_number = getDig(val, digit)
            radix[dig_number].append(val)

        result = []
        for values in radix:
            result.extend(values)
            if len(values) == len(arr):
                can_exit = True
                break
        digit += 1
    return result


arr = [567, 654, 124, 457, 830, 911, 1324, 555, 41, 32, 13, 1]
result = radix_sort_for_integer(arr)
print(result)
#시간복잡도 : O(dn) = O(n)
#제자리성 : 제자리 정렬 아님. 진법 만큼의 메모리 필요. + 추가 메모리 필요할 수도 있음.
#안정성 : 안정적. 순서대로 뒤쪽 레코드부터 뒤에 배치

• 시간복잡도 : O(dn). 각 자릿수 * 원소 개수 만큼의 비교가 필요하다.
• 제자리성 : radix가 가질 수 있는 값의 범위만큼의 공간이 필요하다.
• 안정성 : 마지막 radix 을 시작으로 각 단계에서는 순서가 변경되지 않으므로 안정적이다.

버킷 정렬

기수정렬을 일반화한 방식.  각 버킷의 범위에 따라 원소들을 분포하여 삽입하되, 각 버킷에서는 안정적 정렬 알고리즘을 이용하여 순서를 정한다. 이후 정렬된 버킷들을 결합하여 전체를 정렬하게 되는 알고리즘이다. 입력된 키의 값이 특정한 범위 내에서 변화하며, 확률적으로 균등히 분포되어 있을 때 사용한다.

코드

"""
키 값이 0~1 사이에 균일하게 분포한다고 가정, 하나의 버킷에 하나의 키만 들어있을 확률이 높다.

"""

"""
@input insertion_sort을 통해 
"""
def by_insertion_sort(arr: list[float], value: float):
    insert_idx = len(arr) - 1

    while insert_idx >= 0 : 
        if arr[insert_idx] <= value:
            break
        insert_idx -= 1
    insert_idx += 1
    if insert_idx == len(arr) : 
        # 가장 큰 원소라면 값을 추가
        arr.append(value)
    else: # 아니면 값을 특정 인덱스 자리에 삽입
        arr.insert(insert_idx, value)

    #리스트의 insert 함수는 지정된 인덱스 "앞에" 값을 넣는다.

def bucket_sort(arr: list[float]):
    bucket = [[] for _ in range(10)] #데이터가 담길 버킷

    for val in arr :  # arr에 담긴 값들에 대해
        idx = int(val * 10) # 값에 대한 "내림" 인덱스를 적용한다.
        by_insertion_sort(bucket[idx], val)
    print(bucket)
    result = []

    for temp in bucket:
        result.extend(temp)
    return result

arr = [0.86, 0.32, 0.27, 0.12, 0.49, 0.21, 0.62, 0.89, 0.71, 0.87]

arr = bucket_sort(arr)
print(arr)

• 시간복잡도 : 평균 O(n), 최악 O(n²). 모든 원소가 하나의 버킷에 몰리면 비교 기반 정렬만이 수행된다.
• 제자리성 : 입력된 배열의 원소들을 저장하기 위한 버킷 공간이 배열 크기에 비례하게 필요하다.
• 안정성 : 삽입 정렬과 같은 비교 기반 정렬에 기반하므로, 안정적으로 정렬이 수행된다.