계수정렬이란?? (계수정렬 예시)

계수정렬이란?

---

• 계수정렬이란, 데이터의 크기만큼 배열(python는 list)를 선언하여 데이터의 개수를 카운터 해 맞는 인덱스를 증가시켜 나열하는 정렬
• 모든 데이터 값이 정수여야 함 (값의 범위가 무한한 실수는 불가능, 양의 정수일 때 많이 사용)
• 데이터의 값이 0~100정도의 작은 값일 때 사용
• MAX데이터의 값과 MIN데이터의 값이 1,000,000을 넘지 않을 때 사용

예시

---

0 부터 100까지 성적이 엄청 많이 있을 때, 이 성적을 정렬 할 때 유용

과정

---

1. 성적 리스트의 값 중 최고점 개수만큼 리스트를 선언한다.
2. 성적 리스트를 돌며 점수에 맞는 인덱스의 count를 +한다.
3. 출력하거나 list를 합친다.

코드 예시

---

score = [100, 50, 23, 47, 99, 66, 1, 0, 0, 20, 50, 52, ...]

count = [0] * (max(score) + 1)  # 이경우 100 + 1

for i in range(len(score)):  # score의 개수만큼 ++
    count[score[i]] += 1

for i in range(len(count)):  # 출력
    for j in range(count[i]):
        print(i, end=' ') 

-> 데이터의 최소값과 최대값이 차이가 많지 않으면 제일 빠르게 정렬 가능, 차이가 커지면 공간복잡도(메모리 상 효율)이 매우 떨어지게 됨