[자료구조] 계수 정렬(Counting Sort)

목차

 정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

계수 정렬(Counting Sort)

개념

• non-comparison 기반 정렬에서 가장 간단한 정렬 방법입니다. 
• 주어진 값의 범위가 한정적일 때 유용한 방법입니다. 주어진 값의 범위에 대한 count 배열을 생성해 줍니다. 그 후 해당 count 배열을 앞에서부터 누적합을 계산해 줍니다. 이럴 경우 이제 배열에서 특정값에 대한 시작 인덱스를 확인할 수 있습니다. 자세한 내용은 아래 참고
• 시간복잡도는 O(n+k)로 값의 범위(k)(최댓값과 최솟값의 차이)가 작으면 일반적인 정렬 방법인 O(nlogn) 보다 빠를 수 있습니다.
• 

코드

• counting sort

  • def counting_sort(arr):
        shift = min(arr)
        K = max(arr) - shift + 1
        counts = [0 for _ in range(K)]
        for item in arr:
            counts[item - shift] += 1
    
        starting_index = 0
        for i, count in enumerate(counts):
            counts[i] = starting_index
            starting_index += count
    
        sorted_arr = [0 for _ in range(len(arr))]
    
        for item in arr:
            sorted_arr[counts[item - shift]] = item
            counts[item - shift] += 1
    
        return sorted_arr
    
    
    arr = [7, 3, 2, 5, 6, 10, 9, 8, 1]
    arr = counting_sort(arr)
    print(arr)

출처

• https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4437/