반응형
Sort
-
radix + counting sort(기수정렬)카테고리 없음 2020. 1. 30. 21:28
흔히 기수정렬이라고 불리는 radix sort는 다른 정렬과는 달리 값들을 명시적으로 비교하지 않고 정렬하는 방법이다. 그리고 radix sort는 counting sort를 이용하기 때문에 같이 살펴보도록 한다. 사실, 그동안 radix sort의 존재는 알았으나 보통 정렬문제는 quick, merge sort를 사용하기 때문에 자세히 살펴보지 않았으나 특정문제는 풀어내는데 있어서 radix sort의 필요성을 느끼게되었다. Counting sort 정렬해야할 대상인 A가 아래와 같이 있다. A = [1, 4, 1, 2, 7, 5, 2] 먼저, counting sort는 입력값에서 각 숫자의 빈도수를 counting array에 저장을 해야한다. C = [0, 2, 2, 0, 1, 1, 0, 1, 0,..
반응형