Counting Sort

yijin3018·2021년 11월 11일
0
  • 개념 : 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.
  • 작동 원리
    1. 리스트의 개수를 인덱스마다 저장
    2. 누적합을 구함
    3. 리스트 거꾸로 탐색 시작
    4. 리스트의 원소를 인덱스로서 계수리스트에서의 값을 해당 위치에 표현함
  • 특징
    • 누적합 구하기 위해 입력 배열의 최대값 필요함
    • stable sort
  • 장점
    • 매우 빠르게 정렬 가능 - 비교 하지 않기 때문
  • 단점
    • 배열 인덱스 사용하기 때문에 정해진 범위에 한정한 정렬
    • 결과 저장할 추가적 메모리 필요
  • 시간복잡도 : O(nK)O(nK) (K : 원소의 최대값)
  • 공간복잡도 :O(n+K)O(n+K)
a = [2,0,1,2,3,0,2]

def counting_sort(list, s_list):
    cnt = [0] * (max(list) + 1)
    
    for i in list:
        cnt[i] += 1
        
    for idx in range(1, len(cnt)):
        cnt[idx] += cnt[idx-1]

    for j in range(len(a)-1, -1, -1):
        s_list[cnt[a[j]] - 1] = a[j]
        cnt[list[j]] -= 1
        
sorted_list = [0] * len(a)        
counting_sort(a, sorted_list)
print(sorted_list)
profile
💻 For Computer Science..

0개의 댓글