[Algorithm] Counting Sort(계수 정렬)

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

 

인프런 강의 12강에 대한 리뷰이다.

 

계수 정렬은 범위 조건이 있는 정렬이다.

 

강의에서 나온 조건의 경우 "5이하의 수를 정렬"이었다.

 

Counting Sort의 경우 조건에 맞는 수가 몇 개인지 (주어진 숫자 전체를 훑으며) 센 다음 수를 나열하기 때문에

시간복잡도는 O(N) 이다.

 

 

** C++

 

#include <stdio.h>

int main(void) {
	int temp;
	int count[5]; 
	int array[30] = {
		1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
		3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
		3, 1, 4, 3, 5, 1, 2, 1, 1, 1
	};
	for (int i = 0; i < 5; i++) {
		count[i] = 0;
	}
	for (int i = 0; i < 30; i++) {
		count[array[i] - 1]++;
	}
	for (int i = 0; i < 5; i++) {
		if (count[i] != 0) {
			for (int j = 0; j < count[i]; j++) {
				printf("%d",i + 1 );
			}
		}
	}
	return 0;
}

 

 

** Javascript

 

위 C++ 소스를 Javascript 로 바꾸면 아래와 같다.

 

 

function countingSort() {
    let count = new Array(5).fill(0);
    let array = [
        1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
        3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
        3, 1, 4, 3, 5, 1, 2, 1, 1, 1
    ];
    for (var i = 0; i < array.length; i++) {
        count[array[i] - 1]++;
    }
    const answer = count.reduce((acc, curr, i) => acc += (curr != 0) ? (`${i + 1}`).repeat(curr) : "", "");
    console.log(answer);
}

countingSort();

 

reduce 만세

 

 

 

 

 

** Java

 

public class Main
{
    public static void main(String[] args) {
	    int[] count = {0, 0, 0, 0, 0};
	    int[] array = {
            1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
            3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
            3, 1, 4, 3, 5, 1, 2, 1, 1, 1
        };
        for (int i = 0; i < array.length; i++) {
            count[array[i] - 1]++;
        }
        for (int i = 0; i < count.length; i++) {
            if (count[i] != 0) {
                for (int j = 0; j < count[i]; j++) {
                    System.out.printf("%d",i + 1 );
                }
            }
        }
    }
}