계수정렬
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