[Python] 계수 정렬과 기본 정렬 비교

계수 정렬이 사용 가능할 때 계수 정렬과 기본 정렬을 비교해보고 싶어서 테스트

테스트한 문제는 성적 정렬

 

import time
import random


str_pool = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

counting_score = 0
default_score = 0

for i in range(7):
    n = 10**i
    
    #계수 정렬
    scores = [""] * 100
    answer = ""

    random.seed(0)

    start = time.time()
    for _ in range(n):
        name, score = random.choice(str_pool), random.randint(1,100)
        
        scores[score-1] += name + " "

    #answer = "".join(scores)
    counting_score = time.time() - start



	#기본 정렬
    random.seed(0)

    array = []
    answer = ""

    start = time.time()
    for _ in range(n):    
        name, score = random.choice(str_pool), random.randint(1,100)
        array.append((name+" ",score))

    array.sort(key=lambda x: x[1])

    #answer = "".join([s[0] for s in array])
    
    default_score = time.time()-start

    print("N : ", n)
    print("Counting Sort : ", counting_score)
    print("Default Sort : ", default_score)

출력까지 하면 너무 길어지므로 출력은 제외 N의 수를 10배씩 늘려가며 테스트해봤음.

N :  1
Counting Sort :  0.0
Default Sort :  0.0
N :  10
Counting Sort :  0.0
Default Sort :  0.0
N :  100
Counting Sort :  0.0
Default Sort :  0.0009715557098388672
N :  1000
Counting Sort :  0.006997823715209961
Default Sort :  0.008005142211914062
N :  10000
Counting Sort :  0.06696128845214844
Default Sort :  0.07398581504821777
N :  100000
Counting Sort :  0.7178256511688232
Default Sort :  0.5610604286193848
N :  1000000
Counting Sort :  6.682402610778809
Default Sort :  5.43698525428772

N이 10000 이하일때는 계수 정렬이 미세하게 빠르지만 100000이 넘어가는 순간 차이가 역전(+빠르게 격차가 벌어짐)되는 것이 보인다.

몇번을 테스트 해봤는데 그 때마다 차이는 조금 있지만 대체로 비슷한 느낌이었다.

그렇지만 차이가 너무 미세해서 딱히 계수 정렬을 쓰는 메리트를 모르겠는 느낌... 이 문제 한정인지는 모르겠지만!