[5.27] 06-9 도수 정렬

counting sort - 원소의 대소관계를 판단하지 않고 정렬하는 알고리즘

[도수 정렬 알아보기]

step 1. 도수 분포표 만들기

도수 분포표 - 등급으로 나누고, 각 등급에 속하는 도수(자료의 개수)를 나타낸 표

step 2. 누적 도수 분포표 만들기

0부터 n점까지 몇 명이 있는지 누적된 값을 나타내도록 도수 분포표를 만든다

step 3. 작업용 배열 만들기

step 4. 배열 복사하기

#도수 정렬 알고리즘 구현하기

from typing import MutableSequence

def fsort(a:MutableSequence, max:int) -> None:
  n = len(a)
  f = [0] * (max+1)
  b = [0] * n

  for i in range(n):  f[a[i]] += 1
  for i in range(1, max+1): f[i] += f[i-1]
  for i in range(n-1, -1, -1): f[a[i]] -= 1; b[f[a[i]]] = a[i]
  for i in range(n): a[i] = b[i]

def counting_sort(a:MutableSequence) -> None:
  fsort(a, max(a))

if __name__=='__main__':
  print('도수 정렬을 수행합니다')
  num = int(input('원소 수를 입력하세요: '))
  x = [None] * num

  for i in range(num):
    while True:
      x[i] = int(input(f'x[{i}]: '))
      if x[i] >= 0:
        break
  
  counting_sort(x)
  print(x)