[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 17

* 수업은 JS 기반이지만 Python으로 구현

Section 17

기수 정렬: 소개

비교를 수행하지 않으며, 숫자로 작동하는 알고리즘이다. 실제로는 이진수를 이용하며, 문자열이나 이미지 또한 이진 형식으로 바꾸어 활용할 수 있다. 요소간에 절대 비교하지 않는다. 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한다.

열 개의 각기 다른 버킷을 만들고 기수가 10인 한 자리수로 가능한 모든 숫자, 0에서 9를 나타낸다. 가장 오른쪽 숫자에 맞추어 버킷에 분류한다. 버킷 내부에서는 정렬하지 않은 채로 버킷에 분류된 순서를 유지하면서 다시 목록을 구성한다. 이후 다음 왼쪽 자릿수에서 이 과정을 반복한다. 목록을 재구성한 후 다시 그 다음 왼쪽 자릿수에서 이 과정을 반복한다. 이때 목록의 순서에 따라 버킷에 분류되어야 하며, 목록을 재구성할 때에도 버킷에 먼저 들어간 순서대로 나와야 한다. 과정의 반복 횟수는 가장 큰 수의 자릿수에 달려있다.

버킷의 숫자는 몇 진수인지에 따라 달려있다. 10진수에서는 10개를, 2진수에서는 2개를 활용한다. 

getDigit(num, place): 소개 및 구현

• 수와 위치를 가져온 다음 그 위치의 숫자를 반환한다.
• method 만드는 두 가지 방법
  • 문자열로 변환한 다음 올바른 인덱스를 사용하여 원하는 수에 적용하고 다시 수로 변환할 수 있다. 문자열 인덱스는 왼쪽부터 시작하므로 유의해야 한다.
  • 10진법에서 각 수의 자릿수 10의 거듭제곱을 나타낸다.

# getDigit
def getDigit(num, place):
    # 주어진 수를 원하는 자릿수의 윗 자리수의 10의 제곱값으로 나눈 나머지를
    # 원하는 자릿수의 10의 제곱값으로 나누어 몫을 구한다.
    # 음수인 경우도 있을 수 있으므로 절댓값 처리를 해준다.
    return abs(num) % pow(10, place + 1) // pow(10, place)
    
getDigit(382, 1)

digitCount(num): 소개 및 구현

• 주어진 숫자 목록을 실행하는 횟수는, 주어진 숫자 목록 중 가장 큰 수의 자릿수에 달려있다.
• 가장 큰 숫자에 자릿수가 얼마나 되는지 알아내는 것이다.
• 0부터 가장 큰 자릿수까지 루프를 만들 진행마다 다음의 일을 수행한다.
  
  • 0부터 9까지의 버킷을 만든다.
  • 각 숫자를 맞는 버킷에 넣는다.
• 0부터 9까지 버킷에 들어있는 요소들의 위치를 사용하여 목록을 재정렬한다.
• 배열을 반환한다.

# digitCount
def digitCount(num):
    # 만약 입력값이 0이라면 0 return
    if num == 0:
        return 0
    # log 함수를 사용하기 위해 math 라이브러리를 불러온다.
    import math
    # math의 log 함수 중 밑이 10인 것의 지수값을 구해
    # math의 ceil함수를 이용, 정수 올림처리를 한다.
    # 만약 자릿수가 3일 경우, 목록을 3번 반복해야하기 때문이다.
    # 이때 입력값이 음수일 경우가 있으므로 절댓값 처리를 한다.
    return math.ceil(math.log10(abs(num)))



digitCount(-3)
digitCount(3131)
digitCount(0)

mostDigits(arr): 소개 및 구현

• 배열에서 가장 큰 수의 자릿수를 반환한다.

# mostDigits(arr)
def mostDigits(arr):

    # digitCount
    def digitCount(num):
        # 만약 입력값이 0이라면 0 return
        if num == 0:
            return 0
        # log 함수를 사용하기 위해 math 라이브러리를 불러온다.
        import math
        # math의 log 함수 중 밑이 10인 것의 지수값을 구해
        # math의 ceil함수를 이용, 정수 올림처리를 한다.
        # 만약 자릿수가 3일 경우, 목록을 3번 반복해야하기 때문이다.
        # 이때 입력값이 음수일 경우가 있으므로 절댓값 처리를 한다.
        return math.ceil(math.log10(abs(num)))

    # 가장 큰 자릿수 값을 0이라고 선언하여
    # 이후 숫자와 비교한다.
    Most = 0

    # 배열의 요소를 차례대로 digitCount에 넣고, Most값과 비교하여
    # 더 큰 값을 Most에 할당한다.
    for i in arr:
        Most = max(Most, digitCount(i))

    # Most를 반환한다.
    return Most

mostDigits([2, 12, 42, 2123, 43, 322])

기수 정렬: 구현

• 수 목록을 받는 함수를 정의한다
• 가장 큰 수가 몇 자리인지 알아낸다
  • 리스트의 하위 그룹의 요소들을 하나의 리스트로 합치는 방법은 sum함수를 이용하는 것이다. 이 블로그를 참조!

# RadixSort
def Radix(arr):
    # mostDigits(arr)
    def mostDigits(arr):

        # digitCount
        def digitCount(num):
            # 만약 입력값이 0이라면 0 return
            if num == 0:
                return 0
            # log 함수를 사용하기 위해 math 라이브러리를 불러온다.
            import math
            # math의 log 함수 중 밑이 10인 것의 지수값을 구해
            # math의 ceil함수를 이용, 정수 올림처리를 한다.
            # 만약 자릿수가 3일 경우, 목록을 3번 반복해야하기 때문이다.
            # 이때 입력값이 음수일 경우가 있으므로 절댓값 처리를 한다.
            return math.ceil(math.log10(abs(num)))

        # 가장 큰 자릿수 값을 0이라고 선언하여
        # 이후 숫자와 비교한다.
        Most = 0

        # 배열의 요소를 차례대로 digitCount에 넣고, Most값과 비교하여
        # 더 큰 값을 Most에 할당한다.
        for i in arr:
            Most = max(Most, digitCount(i))

        # Most를 반환한다.
        return Most

    # getDigit
    def getDigit(num, place):
        # 주어진 수를 원하는 자릿수의 윗 자리수의 10의 제곱값으로 나눈 나머지를
        # 원하는 자릿수의 10의 제곱값으로 나누어 몫을 구한다.
        return abs(num) % pow(10, place + 1) // pow(10, place)

    # 루프 반복 숫자
    Most = mostDigits(arr)    

    # 가장 자릿수가 큰 숫자만큼 반복
    for i in range(Most):
        # 0에서 9까지 대응하는 숫자가 들어갈 버킷
        buckets = [[] for i in range(10)]
        # 주어진 배열 요소의 가장 낮은 자리 숫자부터 순차적으로 그 값을 확인하여
        # 대응하는 버킷에 순차적으로 배정한다.
        for j in arr:
            # 주어진 숫자의 특정 자릿수의 숫자값
            digit = getDigit(j, i)
            # 알맞는 번호의 버킷에 그 숫자를 넣는
            buckets[digit].append(j)

        # 함수 작동 확인 요소
        print('버킷별 요소: ', buckets)
        
        # 버킷들 요소를 순차적으로 다시 배열에 배정하기
        arr = sum(buckets, [])
            
        # 함수 작동 확인 요소
        print('수정된 배열: ', arr)

    return arr
    
Radix([2, 18, 42, 2123, 47, 325, 61, 1289, 504, 366])

기수 정렬: 빅오 복잡도

n은 정렬할 항목 수나 정수의 수이고 k는 이러한 수의 길이이다.

• 시간복잡도
  • Best: O(nk)
  • Average: O(nk)
  • Worst: O(nk)
• 공간복잡도
  • O(n+k)