Algorithm. 계수정렬

Algorithm 계수(Counting)정렬

이번에는 계수정렬입니다. 특히나 계수정렬은 이름에서 어떤 알고리즘 방식을 이용하는지 쉽게 짐작을 할 수 있습니다.

Counting Sort. 다른건 제치더라고 일단 무언가를 셈을 하고 있다고 예상됩니다.

[1, 1, 3, 0, 2, 2, 4, 4, 1, 3, 3]

이러한 배열을 정렬 해 보겠습니다.

[0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4]

계수 정렬을 사용하여 아래와 같은 값으로 정렬을 했습니다.

이제 이 정렬이 어떻게 이루어지는지 차례로 알아보겠습니다.

1. 계수 정렬은 배열에 각 수가 얼마나 들어있는지를 세어봅니다.

   (이러한 이유로 계숲 정렬이라고 불립니다.)

   위의 배열에는

   0 은 1개,

   1 은 3개,

   2 는 2개,

   3 은 3개,

   4 는 2개

   가 들어 있습니다.

2. 그리고 이렇게 세어진 갯수를 작은 수의 갯수부터 차례로 배열로 만들면

   [1, 3, 2, 3, 2]

   가 됩니다.

3. 이제 갯수를 센 정렬에 누적합을 구합니다.

   갯수배열의 첫번째 있는 수는 누적이 자기자신뿐이니 첫번째에 1이 위치합니다.

   두번째 수는 첫번째 1개와 두번째 3개를 합하여 두번째 위치에 4가 들어갑니다.

   이런 식으로 누적을 진행합니다.

   [1, 4, 6, 9, 11]

   누적합의 결과입니다.

   누적합의 이유는 처음 대상이 되는 배열의 갯수를 세어보면 알 수 있습니다.

   갯수를 센 배열의 첫번째 값이 1인 이유는 0이라는 수가 1개이기 때문입니다.

   두번째 값이 3인 이유는 대상 배열에서 1이 3개가 있었기 때문입니다.

   누적한 결과 값이 새롭게 정렬된 배열에서의 저장 위치를 나타내는 역할을 하기 때문입니다.

4. 마지막으로 누적값만큼 존재하는 값을 새로운 배열에 정렬시켜 입력합니다.

   [0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4]

참고사이트: www.zerocho.com/category/Algorithm