계수 정렬.

정렬 방법론.

1. 원소들의 갯수를 세어 배열 count에 저장한다.

2. 갯수된 정보를 바탕으로 배열을 재구성한다.

특징.

1. 입력 키가 일정한 범위, ex) 1~M사이의 정수로만 이루어져 있다는 것을 미리 알고 있는 경우에 사용 가능하다.

2. 추가 기억장소가 필요하다.

시간 복잡도 : O(N) (중복된 for반복문이 없음.)

10만개로 돌렸음에도 불구하고 빠르다.

# -*- encoding: cp949 -*-
import time
import random
   
N = 100000
M = 1000

def swap(a,i,j):
    a[i],a[j] = a[j],a[i]
   
def CheckSort(a,n):
    Sorted = True
    for i in range(n):
        if a[i] > a[i+1]:
            Sorted = False
        if not Sorted:
            break
    if Sorted: print '정렬 완료.'
    else: print '정렬 오류 발생.'
 
def CountingSort(a,n,m):
    b = [0 for i in range(n+1)]
    count = [0 for i in range(m+1)]
    for j in range(1,m+1):
        count[j] = 0
    for i in range(1,n+1):
        count[a[i]] += 1
    for j in range(2,m+1):
        count[j] += count[j-1]
    for i in range(n,0,-1):
        b[count[a[i]]] = a[i]
        count[a[i]] -= 1
    for i in range(1,n+1):
        a[i] = b[i]
 
def main():
    a = [random.randint(1,65536)%M+1 for i in range(0,N+1)] #랜덤한 10000개의 데이터
    a[0] = -1
    start_time = time.time()
    CountingSort(a,N,M)
    print '(랜덤)힙 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

   
    a = [i%M+1 for i in range(0,N+1)] #정렬된 10000개의 데이터 #리커전이 너무 많이 일어나서 랜덤한 데이터밖에 정렬이 안된다.
    a[0] = -1
    start_time = time.time()
    CountingSort(a,N,M)
    print '(최고)힙 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
  
    a = [i%M+1 for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
    a[0] = -1
    start_time = time.time()
    CountingSort(a,N,M)
    print '(최악)힙 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
if __name__=='__main__':
    main()