조건을 만족할때 매우 빠른 정렬 - counting sort

1. counting sort(카운팅 정렬)

 

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

 

하지만 제한사항이 있다

 

정수나 정수로 표현할 수 있는 자료에 대해서만 적용가능하다

 

- 각 항목의 발생 횟수를 기록하고자 정수로 인덱스 되는 카운팅 배열을 사용하기 때문

 

카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다.

 

전제조건이 중요함

 

예를 들어 "0에서 1000이하의 정수이다" 이런 제한조건을 알고 있어야함

 

음수있으면 안된다는데.. 있어도 될것 같기는 한디

 

시간복잡도는 O(n+k)의 선형시간(n은 리스트의 길이, k는 정수의 최댓값)

 

2. 알고리즘 과정

 

2-1) 주어진 리스트에 등장하는 정수들이 각각 몇개 있는지를 세기 위해 가질 수 있는 정수 최대범위 길이만큼의 counting 배열을 초기화함

 

2-2) 초기화한 배열을 이용해서 각 정수들이 몇개 있는지 세서 counting 배열을 완성

 

for i in range(n):
    cnt[arr[i]] += 1

 

 

참고로 counting 배열은 통상 그 길이가 백만까지만 사용함

 

그 이상이면 구조상 비효율적

 

------------------------------------------

 

여기서 두가지로 나뉘는데 바로 정렬을 수행하거나, 누적합 배열을 만든다

 

예를 들어 [0,4,1,3,1,2,4,1]을 counting정렬한다고 생각해보자.

 

그러면 counting 배열은 0부터 4까지 등장하니까 count_list = [0,0,0,0,0]으로 초기화하면, 각 인덱스 0,1,2,3,4에 대응되는 값들은 각 정수가 발생한 개수이다.

 

그러므로 count_list = [1,3,1,1,2]이고, 이것만 보고도 바로 정렬을 수행할 수 있다

 

0이 1개이니까 0

 

1이 3개이니까 0,1,1,1

 

2가 1개니까 0,1,1,1,2

 

3이 1개니까 0,1,1,1,2,3

 

4가 2개니까 0,1,1,1,2,3,4,4

 

--------------------

 

근데 누적합 배열은 튜플같은 원소를 가진 리스트를 정렬할때 활용하는 것 같다

 

https://blog.naver.com/jqkt15/222031601969

[알고리즘] Counting Sort for Stable Sort - Pair Type (ppt, 소스코드)

 

보니까 지금 건들일만한 알고리즘 수준은 아닌것 같은데??

 

튜플의 두번째 원소를 counting sort하는데, 원소의 index를 저장한 정렬 배열을 만들고

 

이를 활용해서 튜플의 첫번째 원소를 counting sort한다네

 

어렵다.. 나중에 보이면 건들이도록 하고

 

아무튼 튜플이 아닌 원소를 가진 경우도 누적합 배열을 이용해서 정렬할 수 있다는 것도 알고있자고

 

stable한 sorting을 만들어준대

 

첫번째로 나온 1은 첫번째로 들어가고 두번째에 나온 1은 두번째로 들어가고.. 4번째로 나온 1은 4번째로 들어가도록..

 

입력된 순서도 보장해주는 그런 sorting을 위해서는 누적합 배열이 필요하대

----------------------------------------------------------

 

여기서는 누적합 배열을 이용해서 정렬해보도록 한다

 

2-3) 만든 counting 배열의 누적합 배열을 구한다

 

for i in range(1,n-1):
    
    cnt[i] += cnt[i-1]

 

 

 

2-4) 데이터를 뒤에서부터 읽어나가면...

 

예를 들어 [0,4,1,3,1,2,4,1]의 누적합 배열이 [1,4,5,6,8]인데 누적합 배열이 가지는 의미를 좀 생각해보면

 

0번째에 있는 1은 0이 1개 있다는 의미이고, 0

 

1번째에 있는 4는 0과 1의 개수 합이 4라는 뜻으로 0,1,1,1로 된다는 의미겠지

 

그러면 뒤에서부터 읽은 1은, 누적합 배열의 첫번째 4에 접근하는데..

 

뒤에서부터 읽었으므로, 1은 모든 1중에서 마지막에 등장하는 1이고 저 4 자체가 바로 이 1의 위치라는 뜻이다

 

 

하나를 정렬했으니까 해당 누적합배열의 4는 1을 빼줘서 3으로 만들고

 

다음에 읽은 4는 누적합배열에서 8이라는 값을 가지는데 8번째에 나온다는 뜻이므로

 

 

역시 4를 하나 정렬했으니까 누적합배열에서 1을 빼줘서 7로 만들고.. 이런식으로 계속 읽어나간다

 

다음에 읽을 2는 5번째 위치에 있다는 뜻이므로

 

 

다음에 나올 1은 3번째 위치에 있다는 뜻이므로

 

 

다음에 나올 3은 6번째 위치에 있다는 뜻이므로..

 

 

다음에 나올 1은 2번째 위치에 있다는 뜻이므로..

 

 

다음에 나올 4는 7번째 위치에 있다는 뜻이므로..

 

 

다음에 나올 0은 1번째 위치에 있다는 뜻이므로..

 

 

뒤에서부터 읽는것은 누적합 배열의 값을 자연스럽게 이용하기 위해서이다.

 

앞에서부터 읽는다고 생각하면.. 복잡한 처리를 해야할것 같다

 

 

3. 예시 코드

 

arr = [0,4,1,3,1,2,4,1]

n = 4

counting_list = [0]*(n+1)

counting_sort_list = [0]*(len(arr))

for i in range(len(arr)):
    
    counting_list[arr[i]] += 1

for i in range(1,n+1):
    
    counting_list[i] += counting_list[i-1]

for i in range(len(arr)-1,-1,-1):
    
    counting_sort_list[counting_list[arr[i]]-1] =arr[i]
    
    counting_list[arr[i]] -= 1

 

 

4. 주의할점

 

counting 배열 생성할 때 인덱스 에러가 나지 않도록 주의하면서 범위조건을 잘 확인하고

 

알고리즘 자체가 인덱스 이동이 심해서 생각을 잘해야함

 

sorting은 기본적으로 O(nlogn)이 가장 빠른데, 일반적으로 제공되는 sort()함수는 이러한 시간복잡도를 가지도록 구현되어있을 것임

 

근데 제약사항으로 리스트의 정수 최댓값 범위를 알고 있고 비교적 작을때 가장 효율적으로 동작할 수 있는게 counting sort