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 |