카운팅 정렬

Counting sort
카운팅 정렬
클래스정렬 알고리즘
데이터 구조배열
최악의 경우 공연( + k) 여기서 k는 음이 아닌 키 값의 범위다.
최악의 경우 공간 복잡성

컴퓨터 과학에서 카운팅 정렬은 작은 양의 정수인 키에 따라 개체 집합을 정렬하기 위한 알고리즘이다. 즉, 정수 정렬 알고리즘이다.그것은 뚜렷한 키 값을 가진 개체의 수를 세고, 그 카운트에 접두사 합계를 적용하여 출력 시퀀스에서 각 키 값의 위치를 결정하는 방식으로 작동한다.실행시간은 항목 수와 최대키값과 최소키값의 차이가 선형이기 때문에 키의 편차가 항목 수보다 크게 크지 않은 상황에서만 직접 사용하기에 적합하다.라딕스 분류에서는 서브루틴으로 자주 사용되는데, 이것은 더 큰 키를 더 효율적으로 다룰 수 있는 또 다른 분류 알고리즘이다.[1][2][3]

카운트 정렬은 비교 정렬이 아니다. 이는 키 값을 배열의 인덱스로 사용하며 비교 정렬에 대한 Ω(n log n) 하한이 적용되지 않는다.[1]버킷 분류는 세는 분류 대신 사용할 수 있으며 유사한 시간 분석을 수반한다.그러나, 계수 정렬과 비교하여 버킷 정렬은 각 버킷 내의 항목 집합을 보유하기 위해 링크된 목록, 동적 배열 또는 많은 양의 사전 할당된 메모리를 필요로 하는 반면, 계수 정렬은 버킷당 하나의 숫자(항목 수)를 저장한다.[4]

입력 및 출력 가정

가장 일반적인 경우, 카운트 분류에 대한 입력은 n개의 항목 모음으로 구성되며, 각 항목에는 최대값이 k인 음수가 아닌 정수 키가 있다.[3]계수 분류에 대한 일부 설명에서, 정렬할 입력은 더 단순한 정수 자체의 배열로 가정되지만,[1] 이러한 단순화는 계수 분류의 많은 응용을 수용하지 않는다.예를 들어, 라딕스 정렬에서 서브루틴으로 사용될 때, 각 호출에서 카운트 소트 소트까지의 키는 더 큰 항목 키의 개별 자릿수가 된다; 항목에서 분리된, 정렬된 키 자릿수 목록만 반환하는 것으로 충분하지는 않을 것이다.

radix sort와 같은 어플리케이션에서, 최대 키 값 k에 대한 바운드는 미리 알 수 있을 것이며, 알고리즘에 대한 입력의 일부라고 가정할 수 있다.그러나 k의 값을 아직 알 수 없는 경우, 첫 번째 단계로서 최대 키 값을 결정하기 위해 데이터에 대한 추가 루프를 통해 k의 값을 계산할 수 있다.

출력은 키로 정렬된 요소의 배열이다.라딕스 정렬에 적용되기 때문에, 계수 정렬은 안정적인 정렬이어야 한다. 즉, 두 요소가 동일한 키를 공유할 경우 출력 배열의 상대적 순서와 입력 배열의 상대적 순서가 일치해야 한다.[1][2]

가성음

유사 코드에서 알고리즘은 다음과 같이 표현될 수 있다.

function CountingSort(input, k)          count ← array of k + 1 zeros     output ← array of same length as input          for i = 0 to length(input) - 1 do j = key(input[i])         count[j] += 1      for i = 1 to k do         count[i] += count[i - 1]      for i = length(input) - 1 downto 0 do j = key(input[i])         count[j] -= 1         output[카운트[j] = 입력[i] 반송 출력

여기input정렬할 입력 배열,key입력 배열에서 각 항목의 숫자 키를 반환한다.count각 키로 항목 수를 저장하기 위해 먼저 사용된 보조 배열이고, 각 키를 가진 항목이 배치되어야 하는 위치를 저장하기 위해 (두 번째 루프 후)k음수가 아닌 키 값의 최대값이며output정렬된 출력 배열.

요약하면 알고리즘은 첫 번째 루프에서 항목 위로 루프되며, 각 키가 발생하는 횟수의 히스토그램을 계산한다.input수집의그 후 두 번째 루프에서 접두사 합계 계산을 수행한다.count각 키에 대해 해당 키를 가진 항목이 배치되어야 하는 위치 범위(즉, i 항목)를 제자리에 배치해야 한다.count[].결국 세 번째 루프에서는 의 항목들을 반복한다.input다시, 그러나 역순으로, 각 항목을 다음에서 정렬된 위치로 이동output대열을 [1][2][3]갖추다

키가 같은 항목의 상대적인 순서는 여기에 보존된다. 즉, 이것은 안정된 종류다.

복잡도 분석

알고리즘은 반복이나 서브루틴 호출 없이 루프에만 단순하게 사용하기 때문에 분석이 간단하다.카운트 어레이의 초기화 및 카운트 어레이에서 접두사 합계를 수행하는 두 번째 루프에 대해 각각 최대 k + 1회 반복되므로 O(k) 시간이 소요된다.나머지 두 개는 루프와 출력 어레이 초기화로 각각 O(n) 시간이 소요된다.따라서 전체 알고리즘의 시간은 이러한 단계의 시간 합인 O(n + k)이다.[1][2]

길이 k + 1과 n의 배열을 사용하기 때문에 알고리즘의 총 공간 사용량도 O(n + k)이다.[1]최대 키 값이 항목 수보다 훨씬 작은 문제 사례의 경우, 입력 및 출력 어레이 외에 사용하는 스토리지가 공간 O(k)를 사용하는 카운트 어레이뿐이기 때문에 계수 정렬은 공간 효율성이 매우 높을 수 있다.[5]

변형 알고리즘

정렬할 각 항목이 정수이고 키로도 사용될 경우, 두 번째와 세 번째 루프를 조합할 수 있다; 키를 가진 항목이 있는 위치를 계산하는 대신 두 번째 루프에서.i출력물에 넣어야 하고, 간단히 덧붙여야 한다.Count[i]그 번호의 사본i생산량까지

이 알고리즘은 또한 중복 키를 제거하는 데 사용될 수 있다.Counta를 저장하는 비트 벡터가 있는 배열one입력 및 A에 있는 키에 대해zero존재하지 않는 열쇠에 대해서 말이야항목이 정수 키 자체인 경우, 두 번째 및 세 번째 루프는 모두 생략할 수 있으며 비트 벡터 자체가 출력 역할을 하여 값을 비-값의 오프셋으로 나타낸다.zero범위의 가장 낮은 값에 추가된 항목.따라서 이 변종에서는 비트 배열로 배치하는 것만으로 키가 정렬되고 중복이 제거된다.

최대 키 크기가 데이터 항목 수보다 현저히 작은 데이터의 경우 입력을 거의 동일한 크기의 하위 배열로 분할하고 각 하위 어레이를 병렬 처리하여 각 하위 어레이에 대해 별도의 카운트 어레이를 생성한 다음 카운트 어레이를 병합하여 카운트 정렬을 병렬화할 수 있다.병렬 라딕스 정렬 알고리즘의 일부로 사용할 경우, 분할 서브레이의 크기와 일치하도록 키 크기(라딕스 표현 기준)를 선택해야 한다.[6]계수 분류 알고리즘의 단순성과 쉽게 병렬화할 수 있는 접두사 합 원시 사용도 보다 세밀한 병렬 알고리즘에서 사용할 수 있게 한다.[7]

기술된 바와 같이, 카운트 정렬은 내부 알고리즘이 아니다. 카운트 배열을 무시하더라도 별도의 입력 및 출력 배열이 필요하다.카운트 어레이만 보조 저장소로 사용하여 입력으로 주어진 배열 내에서 항목들을 정렬된 순서로 배치하도록 알고리즘을 수정할 수 있지만, 개량한 내부 버전의 카운팅 정렬은 안정적이지 않다.[3]

역사

비록 라딕스 분류 자체가 훨씬 더 오래되었지만, 세는 분류와 라딕스 분류에 대한 적용은 둘 다 해롤드 H에 의해 발명되었다. 1954년 Seward.[1][4][8]

참조

  1. ^ a b c d e f g h 181페이지의 기록 노트도 참조하십시오Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "8.2 Counting Sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 168–170, ISBN 0-262-03293-7.
  2. ^ a b c d Edmonds, Jeff (2008), "5.2 Counting Sort (a Stable Sort)", How to Think about Algorithms, Cambridge University Press, pp. 72–75, ISBN 978-0-521-84931-9.
  3. ^ a b c d Sedgewick, Robert (2003), "6.10 Key-Indexed Counting", Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching (3rd ed.), Addison-Wesley, pp. 312–314.
  4. ^ a b Knuth, D. E. (1998), The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Addison-Wesley, ISBN 0-201-89685-0. 제5.2절, 카운트별 정렬, 페이지 75-80, 그리고 역사 노트 170.
  5. ^ Burris, David S.; Schember, Kurt (1980), "Sorting sequential files with limited auxiliary storage", Proceedings of the 18th annual Southeast Regional Conference, New York, NY, USA: ACM, pp. 23–31, doi:10.1145/503838.503855, ISBN 0897910141.
  6. ^ Zagha, Marco; Blelloch, Guy E. (1991), "Radix sort for vector multiprocessors", Proceedings of Supercomputing '91, November 18-22, 1991, Albuquerque, NM, USA, IEEE Computer Society / ACM, pp. 712–721, doi:10.1145/125826.126164, ISBN 0897914597.
  7. ^ Reif, John H. (1985), "An optimal parallel algorithm for integer sorting", Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), pp. 496–504, doi:10.1109/SFCS.1985.9, ISBN 0-8186-0644-4.
  8. ^ Seward, H. H. (1954), "2.4.6 Internal Sorting by Floating Digital Sort", Information sorting in the application of electronic digital computers to business operations (PDF), Master's thesis, Report R-232, Massachusetts Institute of Technology, Digital Computer Laboratory, pp. 25–28.

외부 링크