[TIL_알고리즘] 정렬 알고리즘 Counting Sort

원소간 비교하지 않고 각 원소가 몇번 등장하는지 세는 작업을 하여, 선형 시간에 정렬

정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나 필요

 

before=[5,0,2,4,2,2,4,1]

*정수이고 음수가 아닌 값만 가능

 

1. before에서 각 원소들의 발생 회수를 세고, 카운트 배열 c에 저장

 

    0 1 2 3 4 5 

c  1 1 3 0 2 1

 

for i in range(0,howmany):

  c[before[i]]+=1

 

2. c의 원소를 조정

 

for i in range(1,len(c)):

  c[i] += c[i-1]

 

3. c[1]을 감소(인덱스번호는 0부터 시작하기 때문에)시키고 after에 1을 삽입

 

for i in range(howmany-1,-1,-1):

  c[before[i]] = c[before[i]]-1

  after[c[before[i]]] = before[i]

 

#before배열의 i의 값에 해당하는 인덱스의 값을 c배열의 인덱스 값에서 찾아 -1하고, 그값을 after에 c열의 인덱스 값에 해당하는 인덱스의 값에 삽입

i=7

before[7] = 1

c[1]=1->c[1]=1-1=0

0이 after의 인덱스[1]에 들어갈 값

after[1]=0

 

4. 정렬 작업을 종료

 

---

 

best case: O(n+k)

worst case: O(n+k)

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

*n은 리스트 길이, k는 정수의 최대값

 

 

---

before=[5,0,2,4,2,2,4,1]

howmany=len(before)

after=[0]*howmany

 

c=[0]*10

 

for i in range(0,howmany):

  c[before[i]]+=1

 

for i in range(1,len(c)):

  c[i] += c[i-1]

 

for i in range(howmany-1,-1,-1): 

  c[before[i]] = c[before[i]]-1

  after[c[before[i]]] = before[i]

print(before)

print(after)

 

[5, 0, 2, 4, 2, 2, 4, 1]

[0, 1, 2, 2, 2, 4, 4, 5]