[파이썬] 카운팅 정렬

카운팅 정렬은 계산 복잡성이 O(n)인 알고리즘입니다.

이 게시글은 아래의 블로그를 참고했습니다. 감사합니다.

https://elrion018.tistory.com/37

카운팅 정렬(counting sort) - 정렬 알고리즘, 파이썬

카운팅 정렬 코드는 다음과 같습니다.

def counting_sort(array,max):

    counting_array = [0]*(max+1)
 
    for i in array:
        counting_array[i] += 1
 
    for i in range(max):
        counting_array[i+1] += counting_array[i]
 
    output_array = [-1]*len(array)
 
    for i in array:
        output_array[counting_array[i] -1] = i
        counting_array[i] -= 1
    
    return output_array

 

풀이과정

 

10개의 array [5,5,2,2,4,3,3,1,1,7]가 존재합니다. 이것을 정렬하기 위해 counting_array 와 output_array가 필요합니다.

 

1. 우선 counting_array는 array의 누적 빈도수를 의미합니다. 이것을 구해봅시다.

 

1) 처음에는 빈도수를 구하기 위해 0이 8개(array 의 최대값+1)인 리스트를 생성합니다.

    counting_array=[0,0,0,0,0,0,0,0]

 

2) 빈도수를 구합니다.

    counting_array = [0,2,2,2,1,2,0,1] (array의 빈도수) -> 0이 0개있고,1이 2개있고,..., 6이 0개 있고, 7이 1개 있는 것입니다.

 

3) 누적 빈도수를 구합니다.

      counting_array = [0,2,4,6,7,9,9,10] (array의 누적 빈도수)

 

2. output_array를 구합니다. 여기에서 처음 주어진 array가 정렬된 결과값이 나옵니다.

 

1) 우선 -1을 array 개수만큼 리스트로 설정합니다.

    output_array=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1] (output_array의 초기설정)

 

2) counting_array와 엮어서 output_array를 구해보겠습니다.(CODE를 이용해 설명하겠습니다)

 

CODE

  for i in array:
        output_array[counting_array[i] -1] = i
        counting_array[i] -= 1

 

- array의 첫번째 원소가 5일 때, counting_array[5]는 5일때의 누적빈도수를 의미합니다.

  누적빈도수가 9이기 때문에 output_array[8]은 5입니다.

  counting_array[5]는 9에서 8로 줄어듭니다.

 

output_array=[-1,-1,-1,-1,-1,-1,-1,-1, 5,-1]

 

- array의 두번째 원소가 5일 때, counting_array[5]는 5일때의 누적빈도수를 의미합니다.

  누적빈도수가 8이기 때문에 output_array[7]은 5입니다.

  counting_array[5]는 8에서 7로 줄어듭니다.

 

output_array=[-1,-1,-1,-1, -1,-1,-1, 5, 5,-1]

 

- array의 세번째 원소가 2일 때, counting_array[2]은 2일때의 누적빈도수를 의미합니다.

  누적빈도수가 4이기 때문에 output_array[3]은 2입니다.

  counting_array[2]는 4에서 3으로 줄어듭니다.

 

output_array=[-1,-1,-1, 2, -1,-1, -1, 5, 5,-1]

 

- array의 네번째 원소가 2일 때, counting_array[2]은 2일때의 누적빈도수를 의미합니다.

  누적빈도수가 3이기 때문에 output_array[2]는 2입니다.

  counting_array[2]는 3에서 2로 줄어듭니다.

 

output_array=[-1,-1, 2, 2, -1,-1, -1, 5, 5,-1]

 

- array의 다섯번째 원소가 4일 때, counting_array[4]은 4일때의 누적빈도수를 의미합니다.

  누적빈도수가 7이기 때문에 output_array[6]는 4입니다.

  counting_array[4]는 7에서 6으로 줄어듭니다.

 

output_array=[-1,-1, 2, 2, -1, -1, 4, 5, 5,-1]

 

이와 같이 계산하면 output_array는 [1,1,2,2,3,3,3,4,5,5,7]로 정렬됩니다.