계수정렬

20 Jan 2021 in Algorithms

알고리즘 설명

IDEA : 비교해서 정렬하는게 아니라, 숫자를 세서 나타내는?

count 배열에 체크해준다. 오 잼네

성능 분석

• O(n)

JAVA 코드

static int[] ary = {2,1,2,4,3,5,2,2,3,2,9,7};
static int[] result = new int[ary.length];

public static void main(String[] args) {
    sort1(ary,10);
    System.out.println("결과들 : " +Arrays.toString(result) );
}

public static void sort1(int[] ary, int rng) {
    int[] std = new int[rng];
    for(int i =0;i<ary.length; i++) {
        std[ary[i]]++;
    }
    for(int i =0;i<rng-1;i++) {
        std[i+1] += std[i];
    }
    for(int i=0;i< ary.length;i++) {
        if(std[ary[i]]>0) {
            result[std[ary[i]]-1]= ary[i];
            std[ary[i]]--;
        }
    }
}

PYTHON 코드

def counting_sort(ary, int rng):
    result = [0] * len(ary)
    std = [0] * (rng+1)

    for i in range(len(ary)):
        std[ary[i]] += 1
    
    for i in range(1,std(C)):
        std[i] += std[i-1]

    for i in range(len(ary)):
        result[std[ary[i]]-1] =ary[i]
        std[ary[i]] -= 1

    return result