정렬 알고리즘 - 계수 정렬

계수 정렬

계수 정렬(Counting Sort)은 정렬 알고리즘 중 하나로, 비교를 기반으로 하는 다른 정렬 알고리즘들과는 다르게 정수 범위가 제한된 경우에 매우 효율적으로 동작한다.

동작 방식

1. 최댓값 찾기: 입력 배열에서 최댓값을 찾습니다. 이를 통해 카운트 배열의 크기를 결정한다.
2. 카운트 배열 생성 및 초기화: 최댓값을 기반으로 카운트 배열을 생성하고 0으로 초기화한다.
3. 각 요소의 출현 횟수 세기: 입력 배열을 순회하면서 각 숫자의 출현 횟수를 카운트 배열에 기록한다.
4. 정렬된 결과 출력: 각 숫자의 출현 횟수에 따라 정렬된 결과를 생성하고 반환한다.

복잡도

• 시간 복잡도
  • 최선, 평균, 최악 모두 O(N + K)
  • N은 입력 배열의 크기이며, K는 입력 배열의 최댓값의 범위이다.
  • 입력 배열을 순회하여 각 숫자의 출현 횟수를 카운트 배열에 기록하는 과정은 O(N) 시간이 걸린다.
  • 카운트 배열을 순회하여 출력하는 과정은 O(K) 시간이 걸린다.
• 공간 복잡도
  • 입력 배열의 크기에 비례하는 O(N + K)
  • 여기서 N은 입력 배열의 크기이며, K는 입력 배열의 최댓값의 범위이다.
  • 카운트 배열과 정렬된 결과를 저장하기 위한 추가적인 공간이 필요하다.

장단점

• 장점: 비교 연산을 하지 않기 때문에 다른 정렬 알고리즘보다 빠르다.
• 단점: 입력 배열의 크기와 최댓값의 범위에 따라 메모리 사용량이 매우 커질 수 있다.

예시 코드

def counting_sort(arr):
  # 배열에서 최댓값 찾기
  max_value = max(arr)

  # 카운트 배열 생성 및 초기화
  count = [0] * (max_value + 1)

  # 각 요소의 출현 횟수 세기
  for num in arr:
    count[num] += 1

  # 정렬된 결과 출력
  sorted_arr = []
  for i in range(len(count)):
    print([i] * count[i])
    sorted_arr.extend([i] * count[i])

  return sorted_arr


# 입력 받기
arr = list(map(int, input("공백으로 구분된 숫자들을 입력하세요: ").split()))

# 계수 정렬 수행
sorted_arr = counting_sort(arr)

# 정렬된 결과 출력
print("정렬된 결과:", sorted_arr)