[Algorithm] 계수 정렬 (Counting Sort)

 

 

 

 

계수 정렬 (Counting Sort)

계수 정렬은 비교하지 않는 정렬 알고리즘으로 데이터의 개수를 세서 정렬하는 방식.

 

• 정렬하려는 데이터의 범위를 인덱스로 갖는 빈 배열을 생성한다.
  • 데이터 범위가 0 ~ 99까지라면 크기가 100인 빈 배열을 생성한다.
• 정렬하려는 배열을 순회하면서 데이터에 해당하는 인덱스의 값을 1씩 증가한다.

 

제약 조건

• 데이터의 범위가 0 또는 양의 정수여야 한다.

 

예시

• 배열 [8, 3, 9, 2, 3, 4, 0, 5]를 계수 정렬하는 과정.

 

• 정렬하려는 배열 : 

  • 8

    3

    9

    2

    3

    4

    0

    5

• 계수 배열 :

  • 1

    0

    1

    2

    1

    1

    0

    0

    1

    1

• 인덱스 ↑

  • 0

    1

    2

    3

    4

    5

    6

    7

    8

    9

• 최종 배열 : 

  • 0

    2

    3

    3

    4

    5

    8

    9

 

시간 복잡도  :  O(n + k)   * 데이터의 개수 : n , 데이터의 최댓값 : k  (데이터의 최댓값이 무한대에 수렴하면 시간복잡도도 무한으로 수렴)

 

 

 

def counting_sort(arr):
    max_arr = max(arr)
    count = [0] * (max_arr + 1)
    sorted_arr = list()
    
    for i in arr:
        count[i] += 1
    
    for i in range(max_arr + 1):
        for _ in range(count[i]):
            sorted_arr.append(i)
    
    return sorted_arr