[알고리즘 개념] 카운팅 정렬(Counting Sort, 계수정렬)

시간 복잡도 O(n)을 가지는 빠른 정렬 알고리즘으로 카운팅 정렬 혹은 계수 정렬이라고 부른다.A = 0, 1, 3, 3, 5, 2, 1, 2, 5, 4, 1, 4 라는 배열을 정렬하기 위한 방법을 살펴보자.1. 각 숫자의 등장 횟수를 세어 준다.이를 정수 항목들로 인덱싱 되는 카운트 리스트에 저장한다.count[i] = 숫자 i가 등장한 횟수2. 등장 횟수를 누적합으로 바꾼다. 3. 정렬할 배열을 뒤에서 앞으로 순회하며 정렬된 배열 B의 위치에 넣어준다. 2번 과정에서 구한 누적합이 배열 A의 숫자가 배열 B의 어느 위치에 들어가야할 지를 알려준다.A 배열의 맨 뒤에 있는 숫자인 4를 확인 후, count[4]에 있는 누적합을 확인해서 4가 있어야할 위치..........

[알고리즘 개념] 카운팅 정렬(Counting Sort, 계수정렬)에 대한 요약내용입니다.

자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.

원문링크 : [알고리즘 개념] 카운팅 정렬(Counting Sort, 계수정렬)