[정렬] Counting Sort - JS, Python

계수정렬 알고리즘

• 계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 최악의 경우에도 O(N+K)를 보장한다  **K는 가장 큰 수
• 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능
• 가장 작은 데이터의 차이가 1,000,000을 넘기지 않을 때 효과적으로 사용할 수 있다
• 원소간 직접 비교하지 않고 각 원소가 몇 개 등장하는지 갯수를 세서 정렬하는 방법

1. array data값의 min, max값 찾기

1. 모든 범위를 포함하는 리스트 선언하기 (data의 min~max값 크기만큼, 0으로 초기화)

2. array의 data값을 list의 idx와 매치하여 count 1씩 증가시키기

3. list idx의 count한 값 만큼 차례대로 출력해주기  

Big O

BEST : O(N+K)

WORST : O(N+K) **데이터개수 N, 최대값 크기 K

 

• 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기만큼 반복 수행
• 현존하는 정렬 알고리즘 중에서 기수정렬과 더불어 가장 빠르다고 볼 수 있음
• cf. 보통 기수정렬은 계수정렬에 비해서 동작은 느리지만 처리할 수 있는 정수의 크기는 더 크다. 하지만 알고리즘 원리나 소스코드는 더 복잡.
• 하지만 계수정렬은 심각한 비효율성을 초래할 수도 있다
• ex) 데이터 0과 999,999 단 2개만 존재하는 경우 => 리스트 크기 100만개 되도록 선언해야함
• 계수정렬은 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수 없다.
• 공간 복잡도도 O(N+K)이다

장점

• 시간 복잡도가 O(N)인 엄청난 속도의 알고리즘

단점

• 음수가 아닌 정수의 값만 비교할 수 있어 사용이 제한적
• 입력된 요소들의 최대 수만큼 별도의 공간이 필요하며 따라서는 매우 비효율적인 공간 낭비가 이루어질 수 있음

Python 코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
# 시간 복잡도는 O(N+K)

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

# 이때 시간 복잡도는 O(N)
for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 index증가시킴

# 이 때 시간 복잡도가 O(N + K)
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

JavaScript 코드

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for (let i = 1; i < array.length; i ++) {
    for (let j = i; j > 0; j-- ) {
        if (array[j] < array[j-1]) {
            swap = array[j]
            array[j] = array[j-1]
            array[j-1] = swap
        }
        else {
            break
        }
    }
    console.log(`${i}번째 회전: ${array}`)
}