반응형 Counting Sort1 정렬 알고리즘 3 : 계수 정렬(Counting sort) 세 번째로 알아볼 정렬 알고리즘은 바로 계수 정렬! 계수 정렬은 수의 범위가 적을 때 사용하면 좋은 정렬 알고리즘으로 배열의 가장 큰 값에 따라 시간 복잡도가 달라진다. 배열의 가장 큰 값이 k라고 한다면 O(n+k)의 시간 복잡도를 갖는다. 즉, 입력에 비해서 원소들의 값의 범위가 적다면 계수정렬을 사용하는 것이 효율적인 방법이 될 수 있다! 방법 1. 입력된 배열중 가장 큰 값(k) 찾기 2. k+1 크기의 0으로 초기화된 배열 생성한다. 이는 입력된 배열의 원소가 각각 몇 개가 있는지 셀 배열이다. 3. 배열의 원소를 하나씩 검사하여 2번에서 생성한 배열의 인덱스에 해당하는 값을 1씩 올려준다. (즉, 각 값이 몇 개가 나왔는지 카운팅 해준다.) 4. 각 인덱스를 값만큼 반복하여 출력한다. 예시 배.. 2022. 1. 31. 이전 1 다음 반응형