Python Count Sort 카운트 정렬 알고리즘

Count Sort

말 그대로 통 안에 모든 값들을 넣어 카운트(+1) 한 다음에,

bucket[최소 값 ~ 최대 값], 카운트된 만큼 계속 arr[index] 에 지정하는 방식

# Time Complexity : O(n) | Space Complexity : O(n) | stable
def countSort(arr):
    """
    Args:
        arr (list): Array to sort

    Returns:
        arr (list): Sorted input array
    """    
    minValue = min(arr)
    maxValue = max(arr) - minValue  # 음수 케이스 처리

    buckets = [0 for x in range(maxValue + 1)]

    for i in arr:
        buckets[i - minValue] += 1

    index = 0
    for i in range(len(buckets)):
        while buckets[i] > 0:
            arr[index] = i + minValue
            index += 1
            buckets[i] -= 1

    return arr


arr = [-1, 1, 1, 5, 3, 4, 0, -4, 100, 99, 99, 2, 3, 0]
print(countSort(arr))

속도 비교

테스트 배열을 3번 실행해서, 가장 빠르게 정렬된 시간을 출력하도록 했다.

 

1. 랜덤한 숫자 5000개

array = [randint(-5000, 5000) for i in range(5000)]

# 결과
def: sorted(), 최소 실행 시간: 0.00100초
def: countSort(), 최소 실행 시간: 0.00300초
def: introSort(), 최소 실행 시간: 0.01400초
def: quickSort(), 최소 실행 시간: 0.01800초
def: mergeSort(), 최소 실행 시간: 0.02400초
def: smoothSort(), 최소 실행 시간: 0.03200초
def: timSort(), 최소 실행 시간: 0.03500초
def: heapSort(), 최소 실행 시간: 0.03500초
def: insertSort(), 최소 실행 시간: 1.59100초
def: bubbleSort(), 최소 실행 시간: 2.55200초

1위 : arr.sorted(), 2위 : countSort(), 3위 : introSort()

4위 : quickSort(), 5위: mergeSort(), 6위: smoothSort()

7위 : timSort(), 8위: heapSort(), 9위 : insertSort(), 10위: bubbleSort()

 

2. 거꾸로 정렬된 크기 5000의 배열 (Descending)

array = [i for i in reversed(range(5000))]

# 결과
def: sorted(), 최소 실행 시간: 0.00000초
def: countSort(), 최소 실행 시간: 0.00200초
def: introSort(), 최소 실행 시간: 0.00600초
def: quickSort(), 최소 실행 시간: 0.01400초
def: mergeSort(), 최소 실행 시간: 0.01500초
def: timSort(), 최소 실행 시간: 0.02600초
def: smoothSort(), 최소 실행 시간: 0.02800초
def: heapSort(), 최소 실행 시간: 0.02900초
def: insertSort(), 최소 실행 시간: 2.73700초
def: bubbleSort(), 최소 실행 시간: 3.69000초

1위 : arr.sorted(), 2위 : countSort(), 3위 : introSort()

4위 : quickSort(), 5위: mergeSort(), 6위: timSort()

7위 : smoothSort(), 8위: heapSort(), 9위 : insertSort(), 10위: bubbleSort()

 

3. 정렬된 크기 5000 배열 (Ascending)

array = [i for i in range(5000)]

# 결과
def: sorted(), 최소 실행 시간: 0.00000초
def: insertSort(), 최소 실행 시간: 0.00100초
def: countSort(), 최소 실행 시간: 0.00200초
def: introSort(), 최소 실행 시간: 0.00600초
def: timSort(), 최소 실행 시간: 0.01300초
def: mergeSort(), 최소 실행 시간: 0.01300초
def: quickSort(), 최소 실행 시간: 0.01400초
def: smoothSort(), 최소 실행 시간: 0.03100초
def: heapSort(), 최소 실행 시간: 0.03600초
def: bubbleSort(), 최소 실행 시간: 1.08400초

1위 : arr.sorted(), 2위 : insertSort(), 3위 : countSort()

4위 : introSort(), 5위: timSort(), 6위: mergeSort()

7위 : quickSort(), 8위: smoothSort(), 9위 : heapSort(), 10위: bubbleSort()

 

4. 크기 5000의 부분 정렬된 랜덤 배열

array4 = [randint(-5000, 5000)
              for i in range(5000//3)] + \
        [i for i in range(5000//3)] + \
        [1] + \
        [i for i in reversed(range(5000//3))]

# 결과
def: sorted(), 최소 실행 시간: 0.00000초
def: countSort(), 최소 실행 시간: 0.00300초
def: introSort(), 최소 실행 시간: 0.01200초
def: quickSort(), 최소 실행 시간: 0.01300초
def: mergeSort(), 최소 실행 시간: 0.01800초
def: timSort(), 최소 실행 시간: 0.02100초
def: heapSort(), 최소 실행 시간: 0.03100초
def: smoothSort(), 최소 실행 시간: 0.03100초
def: insertSort(), 최소 실행 시간: 1.31700초
def: bubbleSort(), 최소 실행 시간: 2.35200초

1위 : arr.sorted(), 2위 : countSort(), 3위 : introSort()

4위 : quickSort(), 5위: mergeSort(), 6위: timSort()

7위 : heapSort(), 8위: smoothSort(), 9위 : insertSort(), 10위: bubbleSort()

 

한줄평: 심플하고 엄청 빠른데, 메모리(n)를 많이 잡아먹음.

 

tim Sort : (https://choiseokwon.tistory.com/208)

Intro Sort : (https://choiseokwon.tistory.com/209)