×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형



계수 정렬이란?


정렬되어 있지 않은 Array List를 정렬하기 위해 그 값이 몇개 있는지 세는 작업을 하고, 선형 시간에 정렬하는 알고리즘이다.



계수 정렬 알고리즘은 다음과 같다.


1. 정렬 되어 있지 않은 배열을 받아들인다.


2. 각 값마다 몇개가 있는지 새로운 배열에 적는다.

(즉, 아래 2번의 배열은 1이 2개, 2가 3개, 3이 2개, ... ,7이 1개)


3. 2번 배열을 누적합 하여 7번배열까지 더한다.

(0 + 2 = 2, 2 + 3 = 5 , ..., 9 + 1 = 10)


4. 3번 배열을 이용하여 4번 배열에 각 번호에 맞게 값을 하나씩 주고, -1씩 해준다.


이 과정에 대해서는 아래에 계수 정렬 연습 스크립트를 넣어두겠다.







시간복잡도는 O(n)이다.

 - n개의 숫자를 정렬하는데 걸리는 시간은 O(n)

 - 각 숫자가 나온 횟수를 세는데 O(n)

 - 다시 숫자를 정렬된 리스트에 채워넣는데 O(n)





화면이 잘려 보인다면


사이트를 참조하면 된다.




반응형