[Algorithm] 계수정렬(Counting Sort)

계수정렬(Counting Sort) 

크기를 기준으로 갯수를 세는 알고리즘

갯수를 세는 배열(counting)을 정렬하고자 하는 배열(arr)의 사이즈를 최대값으로 담기도록 설정한다.

배열을 탐색하면서 해당 값을(arr[i]) counting배열에서 인덱스로 하는 갯수를 센다. 

import java.util.Scanner;

public class p07_countingSort {
    public static void countingSort(int[] arr, int max){
        int[] counting = new int[max+1]; // 배열의 사이즈를 최대값이 담기도록 잡는다.

        for(int i = 0; i < arr.length; i++){
            counting[arr[i]]++;
        }

        for(int i = 1; i < max+1; i++){
            if(counting[i] != 0) {
                for(int j = 0; j < counting[i]; j++){
                    System.out.print(i+" ");
                }
            }
        }
    }

    public static void countingSort2(int[] arr, int max){
        int[] sorted_arr = new int[arr.length];
        int[] counting = new int[max+1]; // 배열의 사이즈를 최대값이 담기도록 잡는다.

        for(int i = 0; i < arr.length; i++){
            counting[arr[i]]++;
        }

        int t = 0;
        for(int i = 1; i < max+1; i++){
            if(counting[i] != 0) {
                for(int j = 0; j < counting[i]; j++){
                    sorted_arr[t++] = i;
                }
            }
        }

        for(int x: sorted_arr)
            System.out.print(x+" ");

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 배열 갯수
        int max = sc.nextInt(); // 배열의 최대 값
        int[] arr = new int[n];

        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        countingSort(arr, max);
    }
}

시간 복잡도

O(N)

장점

• 빠르다.

단점

• 배열의 최대 값에 따라 메모리가 많이 필요하다.

 

---

source

https://blog.naver.com/ndb796/221228361368

11. 계수 정렬(Counting Sort)

https://gyoogle.dev/blog/algorithm/Counting%20Sort.html

계수 정렬(Counting Sort) | 👨🏻‍💻 Tech Interview