[정렬 알고리즘] 예제4 - 계수 정렬(Counting Sort)(174p)

[이코테] 예제4 - 계수 정렬(Counting Sort)(174p)

풀이 시간: 5분 이내

 

1) 문제 해결 아이디어

<계수 정렬>

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 떄만 사용할 수 있지만 매우 빠른 정렬 알고리즘(데이터의 개수: n, 최댓값: k)

평균 시간 복잡도: O(n + k)

공간 복잡도: O(n + k)

 

2) 소스코드

# 계수 정렬(Counting Sort)
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array) + 1)  # 모든 범위를 포함하는 리스트

# 오름차순 정렬
for i in array:
  count[i] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end = " ")