계수 정렬 ( counting sort )

주제(Subject)
--------------------------------------------------------
한글(약어) : 계수 정렬()
영어(약어) : counting sort()


관련개념(Related Concepts)
--------------------------------------------------------
정렬
알고리즘
분포기반 정렬


개요(Summary)
--------------------------------------------------------
키가 나타난 횟수를 사용해서 정렬하는 방법. 자료가 일정 범위 안에 있다는 것을 알고 있을 때에만 사용가능함.


본문(Body)
--------------------------------------------------------
1. 계수 정렬의 성질

Counting sort is stable (see sorting algorithm) and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be too large compared to n. As long as k is O(n) the running time of the algorithm is Θ(n).
                                                                   - Wikipedia : Counting Sort

2. 소스코드(pseudo code)

for i ← 1 to k do
    c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]
// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1
                                                            from Rashid Bin Muhammad's Home

3. 시뮬레이션
   1) Counting Sort - Java Applet
      http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html

   2) JavaScript
      http://tide4javascript.com/?s=Counting


모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------
1. Christine Mumford(Computer Science, Cardiff University)
   http://users.cs.cf.ac.uk/C.L.Mumford/

2. Rashid Bin Muhammad(Department of Computer Science, Kent State University)
   http://www.cs.kent.edu/~rmuhamma


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Counting Sort
   http://en.wikipedia.org/wiki/Counting_sort

2. Google Search : type [[counting sort site:*.edu]]@google
   http://www.google.com/search?source=ig&hl=en&q=counting+sort+site%3A*.edu

3. Counting Sort
   http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm