본문 바로가기

알고리즘

Counting Sort

CountingSort - 계수 정렬

양의 정수로 이루어진 배열을 정렬할 때 사용하는 정렬 알고리즘

배열에 들어있는 값들을 세어서, 정렬하는 방식.

ex )     key - value 방식

arr = {5, 2, 3, 6, 7, 3, 4, 6, 9, 10}

countingArr = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} ← size == arr에 들어있는 최대값 + 1

arr의 첫번째 원소는 5 → countingArr[5]++;

arr의 두번째 원소는 2 → countingArr[2]++;

arr의 마지막 원소는 10 → countingArr[10]++;

countingArr = {0, 0, 1, 2, 1, 1, 2, 1, 0, 1, 1}

              ↑ 반대로 유추해보면

 arr에 0 = 0개, 1 = 0개, 2 = 1개, 3 = 2개 ...

구한 countingArr로 누적합을 적용한다. arr[i] = arr[i] + arr[ i -1];

위에 예시를 그대로 가져오면.

 

누적합 하기 전 : countingArr = {0, 0, 1, 2, 1, 1, 2, 1, 0, 1, 1}

누적합 한 후    : countingArr = {0, 0, 1, 3, 4, 5, 7, 8, 8, 9, 10}

모든 요소에 1을 빼주면 countingArr = {-1, -1, 0, 2, 3, 4, 6, 7, 7, 8, 9}

 

나온 결과로 배열을 정렬할 수 있다.

countingArr의 인덱스가 arr에 들어있는 값이 되고,

countingArr[arr[i]]의 값이 arr[i]가 들어가야 될 위치가 된다.

ex )

countingArr = {-1, -1, 0, 2, 3, 4, 6, 7, 7, 8, 9}

countingArr[10] = 9 가 뜻하는 것은 10이 9번 인덱스 위치에

countingArr[4] = 3  가 뜻하는 것은 4는 3번 인덱스 위치에

arr = {5, 2, 3, 6, 7, 3, 4, 6, 9, 10}

countingArr = {-1, -1, 0, 2, 3, 4, 6, 7, 7, 8, 9}

sorted = { , , , , , , , , , , }

반복문을 돌면서 정렬

countingArr[arr[i]] == arr[i]의 위치

countingArr[arr[5]] == 3;

sorted[3] = 5 → sorted = { , , , 5, , , , , , }

countingArr[5]--; → countingArr = {-1, -1, 0, 2, 3, 3, 6, 7, 7, 8, 9}

countingArr[arr[1]] == countingArr[2] == 0

sorted[countingArr[arr[1]] == sorted[0] = arr[1]; → sorted = {2, , , 5, , , , , , }

countingArr[2]-- → countingArr = {-1, -1, -1, 2, 3, 3, 6, 7, 7, 8, 9}

countingArr[arr[9]] == countingArr[10] == 9

sorted[countingArr[arr[9]] == sorted[9] = arr[9]; → sorted = {2, 3, 3, 5, 6, 7, 7, 8, 9, 10} ← 정렬 완료

countingArr[2]-- → countingArr = {-1, -1, 0, 0, 3, 3, 4, 6, 7, 7, 8};

'알고리즘' 카테고리의 다른 글

부분 수열의 최대합  (1) 2024.09.05
합병 정렬 (Merge Sort)  (0) 2024.07.10
삽입 정렬 (Insertion Sort)  (0) 2024.07.10
선택 정렬 (Selection Sort)  (0) 2024.07.08
버블 정렬 (Bubble Sort)  (0) 2024.07.08