기수 정렬.

정렬 방법론.

원소들의 첫,두,~~n번째 자리수 따라 새로운 리스트에 넣는다.

ex) 첫번째의 경우 71은 [1]위치에, 97은 [7]위치에 들어간다.(일의자리 기준)

두번째의 경우 십의 자리수를 기초로 정렬한다.

~~ n의 자리수를 기초로 정렬.

설명이 잘된 블로그 : http://kaheeyah.blog.me/220704468091

# -*- encoding: cp949 -*-
import time
import random
import Queue
   
N = 10000
M = 5

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 digit(d,k):
    temp = 1
    for i in range(1,k):
        temp *= 10
    d /= temp
    d %= 10
    return d

def RadixSort(a,n,m,q):
    for k in range(1,m+1):
        for i in range(1,n+1):
            kd = digit(a[i],k)
            q[kd].put(a[i])
        p = 0
        for i in range(10):
            while not q[i].empty():
                p += 1
                a[p] = q[i].get()
 
def main():
    a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
    a[0] = -1
    Q = [Queue.Queue() for i in range(10)]
    start_time = time.time()
    RadixSort(a,N,M,Q)
    print '(랜덤)기수 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

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