[알고리즘/Python] 계수 정렬 | count sort

계수 정렬 [ count sort ]

- 원소간의 비교가 아닌 각 원소가 몇개 등장하는지 갯수를 세서 정렬

 

시간복잡도 ⏱

 

•     최선의 경우 : O(n + k) 
•     최악의 경우 :  O(n + k)   
•     평균 :  O(n + k)

장점

 

1.  시간 복잡도가 O(n+k) [ k : 원소의 최댓값 ] 으로 퀵정렬, 병학 정렬에 비해 일반적으로 빠르다

 

단점

 

1. 원소의 갯수를 저장할 별도의 공간이 필요하다

2. 원소의 최소값과 최대값의 차이가 클 경우 메모리 낭비를 많이 하게 될 수도 있다.

    🗡 ex) [ 1, 33, 72, 14 ,57 ,99999999] - 이 경우 원소의 갯수를 저장할 공간이 99999999보다 커야하지만 안쓰는 인덱스들이 많이 발생

 

[ python count sort code | 파이썬 계수 정렬 코드 ]

data = list(map(int,input().split()))

count = (max(data)+1) *[0]

for i in range(len(data)):
    count[data[i]]+=1
s = []
for i in range(len(count)):
    for j in range(count[i]):
        s.append(i)

print(s)

---

[ 합병정렬 | Merge Sort ]

[ 힙 정렬 | Heap Sort ]

[ 삽입정렬 | Insertion Sort ]

[ 선택 정렬 | Selection Sort ]

[ 퀵 정렬 | Quick Sort ]