반응형 계수정렬1 계수 정렬(counting sort) 계수 정렬(counting sort)는 키가 일정한 범위, 예를 들어, 1부터 M 사이의 정수로만 이뤄져 있다는 사실을 알고 있을 떄 사용할 수 있는 방법이다. 예를 들어 M = 4 이고 a = [1,2,2,1,3,4,4,1] 일 때 count 라는 배열을 만들어서 각 원소의 개수를 저장한다. j 1 2 3 4 count[j] 3 2 1 2 그리고 이를 누적시켜서 저장한다. j 1 2 3 4 count[j] 3 5 6 8 다음으로 배열 a에서 원소들을 뒤에서부터 하나씩 가져와서 count 리스트에 있는 인덱스에 따라 빈 배열 b로 복사한다. a에서 b로 복사하고 나면 count에 있는 인덱스 값을 하나 감소시킨다. 마지막으로 배열 b에 있는 원소들을 배열 a로 복사한다. 이러한 process 의 ADL은.. 2021. 10. 24. 이전 1 다음 반응형
