계수 정렬(Counting Sort) java

계수 정렬(Counting Sort)

계수 정렬이란?

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.^[1][2][3]

Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log n) lower bound for comparison sorting does not apply to it.^[1] Bucket sort may be used for many of the same tasks as counting sort, with a similar time analysis; however, compared to counting sort, bucket sort requires linked lists, dynamic arrays or a large amount of preallocated memory to hold the sets of items within each bucket, whereas counting sort instead stores a single number (the count of items) per bucket.^[4]

출처: 위키백과 

한마디로 각 숫자가 몇개 있는지 갯수를 세어서 다른 한 배열에 저장한 후에 정렬을 하는 방식이다.  이해가 안되신 분들을 위해서 아래 그림으로 그려놓았다. 

만약 입력 갯수=5 이고, 입력된 수가 numbers = 5, 4, 3, 1, 1 이면 countArr 배열에 갯수를 입력한다. 

예를 들면 5,4,3은 한개, 1은 두개이다. 여기서 한글로 쓴 숫자는 countArr의 index값이다. 

만약 countArr의 index값이 5이면 숫자 5가 countArr[5] 안에 있는 value만큼 있다는 것이다. 

ex) countArr[5]=1 이기 때문에 숫자5는 한개있다. 

ex) countArr[1]=2 이면 숫자 1은 두개다. 

countArr의 크기는 최대값+1 만큼 배열생성을 해주어야한다. 왜냐하면 index값을 최대값이랑 같게 만들어주어야하기 때문이다. 

ex)만약 최댓값이 3이면 countArr의 사이즈는 4이다. countArr의 index는 0,1,2,3,4 이기 때문이다. 

그리고서 아래 그림처럼 countArr의 배열안에 있는 값을 누적해준다. 

그리고 나서 result 배열에 정렬된 값을 넣어준다. 

넣는 방식은 numbers 맨 오른쪽 끝부터 시작한다. 

numbers[4]=1이기 때문에 countArr[1] 값을 찾아간다.

result index = countArr value-1

countArr[1] value = 2 이기 때문에 2-1을 해주어서  result[1]에다가 numbers value를 입력한다. 

이런식으로 numbers[0]까지 반복한다. 

실행한 결과가 잘 나온다. 

첫번째 줄은 몇개를 입력한 것인지, 두번째 줄은 임의의 숫자를 입력한다. 

마지막 결과는 1, 1, 3, 4, 5 가 나왔다.

계수정렬은 선형 시간으로 시간복잡도가 나오는데 안타까운것은 공간 효율성은 떨어진다.

만약 3,2,1,10을 입력한다면 

10이 최댓값이기 때문에 배열의 사이즈는 11개를 만들어야한다. 

package Study;
 
/**
 * Created by heeseoknoh on 01/01/2017.
 */
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main {
    int[] numbers; //입력된 숫자
    int[] countArr;//숫자 세기
    int[] result; //정렬된 후 숫자 저장
    int max = 0;
 
    void inputNumbers() throws IOException {//숫자 입력하기
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        numbers = new int[size];
        for (int i = 0; i < numbers.length; i++) {
            int num = sc.nextInt();
            numbers[i] = num;
            if (max < num) {
                max = num;
            }
        }
    }
 
    int findMaxNumber() {//최댓값 찾기
        int max = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (max < numbers[i]) {
                max = numbers[i];
            }
        }
        return max;
    }
 
    void display() {
        for (int i = 0; i < countArr.length; i++) {
            System.out.print(countArr[i] + " ");
        }
        System.out.println();
    }
 
    void display(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
 
    void sort() throws IOException {
        inputNumbers();
        //int maxNumber = findMaxNumber();//최댓값 저장
        int maxNumber = max;
        countArr = new int[maxNumber + 1]; //0-maxNumber+1만큼 생성
        result = new int[numbers.length];
 
        for (int i = 0; i < numbers.length; i++) {
            //해당하는 숫자 카운터
            countArr[numbers[i]]++;
        }
        //System.out.println("CountArr[]=");
        //display();
 
        for (int i = 1; i < countArr.length; i++) {
            //누적 숫자 더하기
            countArr[i] += countArr[i - 1];
        }
        //System.out.println("누적 배열");
        //display();
 
        for (int i = numbers.length - 1; i >= 0; i--) {
            //정렬하기
            result[--countArr[numbers[i]]] = numbers[i];
            //countArr[numbers[i]]--;
        }
        display(result);
    }
 
 
    public static void main(String[] args) throws IOException {
        new Main().sort();
 
 
    }
}

※필기 한것 필요하시면 받아가세요^^

계수정렬.pdf