계수 정렬

https://unsplash.com/photos/H73k0IUQbn0

계수 정렬에 대해 알아보자.

 

 

 

 

 

---

얻어갈 지식

• 계수 정렬 이해

 

 

 

 

 

계수 정렬

 

계수 정렬은 배열의 인덱스에 숫자의 개수를 카운팅하는 방식으로 정렬한다.

예를 들어, a = [ 1, 1, 0 ]라는 배열이 있으면 배열 크기가 2이며 모든 요소가 0인 배열 b를 선언한 뒤

 

a의  첫 번째 요소가 1이므로 b[1] += 1

a의 두 번째 요소가 1이므로 다시 b[1] += 1

a의 마지막 요소가 0이므로 b[0] += 1

 

해당 과정이 끝나면 배열 b에 있는 0을 제외한 모든 요소를 순서대로 출력하면 된다.

 

정수(-, 0, +)와 문자가 들어있을 때 가능하며 실수가 들어있을 경우(3/2, 0.123 등) 계수 정렬이 어렵다.

 

 

코드로 작성

def count_sort(arr):
    count_arr = [0] * (max(arr) + 1)
    output_arr = [0] * len(arr)
    idx = 0

    for i in arr:
        count_arr[i] += 1

    for i in range(len(count_arr)):
        for j in range(count_arr[i]):
            output_arr[idx] = i
            idx += 1

    return output_arr

 

 

 

시간 복잡도와 보조 공간

• 시간 복잡도는 O(N)이다.
• 보조 공간은 주어지는 어레이의 크기에 비례해서 필요하다.
  수의 개수가 작으며 그 수의 차가 클수록 매우 비효율적인데 이를테면, 1과 10000이 있을 경우 단 두 개의 수를 정렬하는데 필요한 배열의 크기가 10000이 되기 때문이다.

 

 

 

 

 

---

https://velog.io/@gndan4/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%EA%B3%84%EC%88%98-%EC%A0%95%EB%A0%AC

정렬 알고리즘

https://www.geeksforgeeks.org/counting-sort/

Counting Sort - GeeksforGeeks