본문 바로가기
Computer Science/자료구조(Data Structure)

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

by 컴돈AI 2024. 4. 17.

목차

     정렬 종류
    비교 기반 정렬(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)

    출처