[자료구조] 특수정렬 - 계수 정렬, 기수 정렬, 버킷 정렬이란?
🐈⬛계수 정렬(Counting Sort)이란?
- 계수 정렬(Counting Sort)은 비교 기반 정렬 알고리즘이 아닌 정수들의 순서를 결정하는 알고리즘입니다.
- 계수 정렬은 비교 없이 정수들의 개수를 세어 정렬하는 특징이 있습니다.
- 각 요소의 배열 등장 횟수를 count해 누적합으로 나타내는 배열을 만든 뒤, 그 누적합으로 요소들의 index를 알아내 작은 숫자 순서대로 정렬하는 기법입니다.
제약
- 데이터의 값은 양수여야 한다.
- 값의 범위가 너무 크지 않아야 한다. (메모리 사이즈를 넘어서면 X)
계수 정렬의 동작방식
1. 정렬할 배열에 있는 정수들을 스캔하며, 각 정수의 발생 횟수를 세어 count하는 배열을 생성합니다.
2. 배열을 누적합으로 조정 후 각 요소의 값을 이전 요소와 합하여 새로운 값을 할당합니다. 배열은 각 정수가 정렬 결과에서 어디에 위치해야 하는지를 나타내는 인덱스로 사용합니다.
3. 정렬할 배열을 역방향으로 스캔하며, 각 정수를 배열의 값으로 대체합니다. 동일한 정수가 여러번 등장할 경우, 배열에서 해당 정수의 값을 하나씩 감소시키면서 할당합니다. 이렇게하면 정렬 끝 - !
계수 정렬 알고리즘 코드(JAVA)
public class CountingSort {
public static int getMaxValue(int[] arr) {
int max = arr[0];
for(int i = 1; i<arr.length; i++) {
if(arr[i]>max) {
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
int arr[] = {5,3,1,9,10,32,11};
int n = arr.length;
// 배열에서 최대값을 찾는다
int max = getMaxValue(arr);
// 카운트 배열을 생성하고 초기화
int[] count = new int[max + 1];
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 카운트 배열을 누적합으로 조정
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 정렬된 결과를 저장할 임시 배열을 생성
int[] sortedArr = new int[n];
// 원래 배열을 역순으로 스캔하며 정렬
for (int i = n - 1; i >= 0; i--) {
int value = arr[i];
int index = count[value] - 1;
sortedArr[index] = value;
count[value]--;
}
// 정렬된 결과를 원래 배열에 복사
System.arraycopy(sortedArr, 0, arr, 0, n);
//arr출력
for(int num:arr) {
System.out.println(num + " ");
}
}
}- 계수 정렬의 시간복잡도는 입력 배열의 크기와 입력 값의 범위에 따라 결정됩니다. O(n+k)라고 생각하시면 됩니다.
- 계수 정렬은 입력 값의 범위가 제한되어 있을 때 가장 효율적인 정렬 알고리즘 중 하나입니다.
🐵기수 정렬(Radix Sort)이란?
- 기수 정렬은 비교 기반 정렬 알고리즘이 아닌 정렬 알고리즘 중 하나입니다.
- 정수나 문자열과 같은 데이터를 자릿수별로 비교하여 정렬하는 방법입니다. 비교 연산을 사용하지 않고 수행합니다.
기수 정렬의 동작방식
1. 정렬할 데이터의 최대값을 찾습니다. 데이터가 정수인 경우 최대 값은 가장 큰 정수이고, 문자열인 경우 가장 긴 문자열의 길이가 최대 값입니다.
2. 정렬할 데이터를 가장 낮은 자리수부터 가장 높은 자리수까지 비교합니다.
3. 각 자리수에 대해 정렬을 수행하기 위해 안정적인 정렬 알고리즘을 사용합니다.
4. 가장 높은 자리수까지 정렬을 반복하면, 전체 데이터가 정렬된 상태가 됩니다.
예를 들어
| 150, 65, 14, 3, 99, 71, 6 |
입력한 수열 몇 개의 키로 분류될 수 있다. 위와 같은 예제에서는 1의 자리, 10의 자리, 100의 자리 분류할 수 있습니다.
| 150, 71, 3, 14, 65, 6, 99 |
수열의 1의 자리만 보고 정렬했을 때는 이러한 결과가 나오게 됩니다.
| 3, 6, 14, 150, 65, 71, 99 |
수열의 10의 자리만 보고 정렬했을 때는 이러한 결과가 나오게 됩니다.
| 3, 6, 14, 65, 71, 99, 150 |
마지막으로, 수열의 100의 자리만 보고 정렬했을 때 정렬이 되어 있는 것을 확인하실 수 있습니다.
기수 정렬 알고리즘 코드(JAVA)
public class RadixSort {
public static void radixSort(int[] arr, int digit) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
//현재 자리수의 개수를 세어 count배열에 저장
for(int i=0; i<n; i++) {
int num = (arr[i] / digit) % 10;
count[num]++;
}
//count배열을 누적합으로 조정합니다.
for(int i=1; i<10; i++) {
count[i] += count[i-1];
}
//output배열을 원래 배열에 복사합니다.
for(int i=n-1; i>=0; i--) {
int num = (arr[i]/digit) % 10;
output[count[num] -1 ] = arr[i];
count[num]--;
}
//output배열을 원래 배열에 복사합니다.
System.arraycopy(output, 0, arr, 0, n);
}
public static int countDigits(int num) {
if(num == 0) {
return 1;
}
int count = 0;
while (num != 0) {
num /= 10;
count++;
}
return count;
}
public static int getMaxValue(int[] arr) {
int max = arr[0];
for(int i = 1; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
int arr[] = {1,9,10,2,6,7};
//입력 배열에서 최대값을 찾는다
int max = getMaxValue(arr);
//최대값의 자리수를 게산한다.
int maxDigits = countDigits(max);
//각 자리수에 대해 정렬을 수행한다.
for (int digit=1; digit<=maxDigits; digit++) {
countingSort(arr, digit);
}
//arr출력
for(int num:arr) {
System.out.println(num + " ");
}
}
}- 기수 정렬의 시간복잡도는 입력 데이터의 자리수와 버킷 정렬에 사용되는 정렬알고리즘의 시간복잡도에 따라 결정됩니다.
˙입력 데이터의 자리수: d
˙정렬 알고리즘의 시간 복잡도: O(n)
🧺버킷 정렬(Bucket Sort)이란?
- 버킷 정렬은 입력 배열을 일정한 범위를 가진 버킷에 분배하고 각 버킷을 개별적으로 정렬하는 알고리즘입니다.
- 입력 데이터의 분포가 균등하고 데이터가 일정한 범위 내에 분포되어 있을 때 가장 효율적으로 동작하는 정렬 알고리즘 입니다.
버킷 정렬의 동작방식
1. 입력 배열의 최대값과 최소값을 찾습니다. 최대값과 최소값을 사용하여 버킷의 범위를 결정합니다.
2. 입력 배열을 순회하며, 각 요소를 해당하는 버킷에 할당합니다. 이 때 버킷의 인덱스는 입력 요소를 버킷의 범위에 매핑하는 함수를 사용합니다.
3. 각 버킷에 대해 선택한 정렬 알고리즘을 사용하여 개별적으로 정렬합니다.
4. 정렬된 각 버킷의 결과를 순서대로 결합하여 최종 정렬된 배열을 얻습니다.
버킷 정렬 알고리즘 코드(JAVA)
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public static void bucketSort(float[] arr) {
int n = arr.length;
// 버킷을 생성
ArrayList<Float>[] buckets = new ArrayList[n];
for (int i = 0; i < n; i++) {
buckets[i] = new ArrayList<>();
}
// 입력 배열의 각 요소를 해당하는 버킷에 할당
for (int i = 0; i < n; i++) {
int bucketIndex = (int) (n * arr[i]);
buckets[bucketIndex].add(arr[i]);
}
// 각 버킷을 개별적으로 정렬
for (int i = 0; i < n; i++) {
Collections.sort(buckets[i]);
}
// 정렬된 버킷을 결합하여 최종 정렬된 배열
int index = 0;
for (int i = 0; i < n; i++) {
for (float num : buckets[i]) {
arr[index++] = num;
}
}
}
public static void main(String[] args) {
float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f};
bucketSort(arr);
//arr출력
for(float num:arr) {
System.out.println(num + " ");
}
}
}- 버킷 정렬의 시간 복잡도는?
˙입력 데이터를 버킷에 분배하는 단계: O(n)
˙개별 버킷을 정렬하는 단계: 버킷당 O(n^2)또는 다른 정렬알고리즘에 따라 다릅니다.
˙정렬된 버킷을 결합하는 단게: O(n)
기수정렬과 버킷정렬의 차이점
