계수 정렬

앞으로 공부할 정렬 알고리즘
https://www.youtube.com/watch?v=n4kbFRn2z9M&t=7s
https://www.zerocho.com/category/Algorithm/post/58006da88475ed00152d6c4b
1. 선택 정렬
2. 버블 정렬
3. 삽입 정렬
4. 퀵 정렬
5. 병합 정렬
6. 힙 정렬

계수 정렬

• 데이터 자체의 위치를 바꾸지 않고 '크기를 기준'으로 개수를 세서 정렬하는 알고리즘

• 단, 범위 조건이 있는 경우에 한해서 가장 빠름.

• 속도 : O(N)

접근 방법

(참조) https://blog.naver.com/ndb796/221228361368
(참조) https://www.zerocho.com/category/Algorithm/post/58006da88475ed00152d6c4b

• 초기 상태

3,4,0,1,2,4,2,4

• 0단계

// 최대값 4를 기준으로 count 할 배열을 만든다.
let count = [0, 0, 0, 0, 0]

• 1단계

// 첫 숫자가 3이므로
let count = [0, 0, 0, 1, 0]

// 두번째 숫자가 4 이므로 
let count = [0, 0, 0, 1, 1]

// 이런식으로 카운팅해서 카운팅 배열을 만든다.
let count = [1, 1, 2, 1, 3]

• 2단계

// 개수의 카운팅 누적값 배열을 만든다.
let count = [1, 2, 4, 5, 8]

• 3단계 (** 1단계의 카운팅 배열가지고만으로도 만들수도 있을듯?)

// 누적합 과 인덱스 번호를 가지고 최종 결과 배열을 만든다.
let count = [1, 2, 4, 5, 8]

// 인덱스 번호 0은 1개
let result = [0]
// 인덱스 번호 1은 1(=2-1)개
let result = [0, 1]
// 인덱스 번호 2은 2(=4-2)개
let result = [0, 1, 2, 2]
// 인덱스 번호 3은 1(=5-4)개
let result = [0, 1, 2, 2, 3]
// 인덱스 번호 4은 3(=8-5)개
let result = [0, 1, 2, 2, 3, 4, 4, 4]

코드

const countingSort = function(array){
    // 최대 값을 찾는다.
    let maxNum = Math.max(...array)

    // 갯수를 카운트할 배열을 만든다.
    let count = []

    for(let i=0; i <= maxNum; i++){
        count[i] = 0
    }

    // 갯수를 카운트 한다.

    for (let i=0; i<array.length; i++){
        count[array[i]] +=1;
    }

    // 누적 값을 구한다.

    for(let i=0; i<maxNum; i++){
        count[i+1] = count[i+1] + count[i]
    }

    // 인덱스 번호를 기준으로 인덱스 데이터 만큼 결과값을 채운다.
    let result = []
    for(let i=0; i < array.length; i++){
        result[count[array[j]]-1] = array[j]
        count[array[j]] -=1;
    }


    return result
}