[알고리즘] 자료구조 - 특수 정렬 ( 계수 정렬, 기수 정렬, 버킷 정렬 )
이번 글에서는 정렬 중 특수 정렬에 대해서 정리해보겠습니다 !
( 지난 기본 정렬, 고급 정렬에 이어 특수 정렬도 오름차순을 기준으로 설명하겠습니다. )
특수 정렬인 계수 정렬, 기수 정렬, 버킷 정렬에 대한 개념 정리를 하고 예시 코드도 설명하도록 하겠습니다.
계수 정렬 ( Counting Sort )
정렬되지 않은 배열의 수들을 각 수들이 몇번 나왔는지 세고, 순서대로 정렬하는 알고리즘
정렬 과정
배열의 수들이 몇번 나왔는지 세어줍니다.
→ 몇 번 나왔는 지 count한 배열을 순회하여 정렬된 배열에서 몇 번째에 나와야 하는지 기록해줍니다.
아이디어는 굉장히 간단합니다.
정렬할 데이터들이 주어졌을때 각 데이터들의 갯수를 count해주고 몇 번째 나와야 할지 ( 현재 숫자 앞의 숫자의 갯수 : count값 고려 ) 세어주면됩니다.
정렬되지 않은 배열을 해당 값이 몇개 있는 지 count하는 것만 하면 되기 때문에,
시간 복잡도는 O(N)입니다.
기수 정렬 ( Radix Sort )
낮은 자리수부터 비교하여 정렬하는 알고리즘
정렬 과정
0부터 9까지의 Bucket을 준비합니다. ( Queue의 자료구조를 가진 Bucket ) ( Bucket은 자릿수 별로 만들어줍니다. )
→ 모든 데이터에 대해 가장 낮은 자리수에 해당하는 Bucket에 차례로 넣어줍니다.
→ 0부터 차례대로 Bucket에서 데이터를 다시 가져옵니다.
→ 가장 높은 자리수를 기준으로 자리수를 높이면서 위의 과정을 반복해줍니다.
자리수가 고정되어 있기때문에 안정성이 있는 알고리즘이지만, 추가적인 메모리가 많이 필요합니다.
시간 복잡도는 O(N)입니다. ( O(r*N) : r = 숫자의 자릿수 )
버킷 정렬 ( Bucket Sort )
배열의 원소를 여러 Bucket으로 분산하여 정렬하는 알고리즘
정렬 과정
빈 Bucket을 준비합니다.
→ 분산 : 정렬할 배열의 데이터를 각각 Bucket에 넣어줍니다. ( 배열의 데이터 갯수 = Bucket을 등분할 갯수 )
→ 내용물이 있는 Bucket을 각각 정렬합니다.
→ 수집 : Bucket을 순서대로 방문하면서 모든 데이터를 원래 배열에 다시 넣어줍니다.
최악의 경우에는 한 Bucket에 키값이 몰렸을 때, 시간 복잡도보다 오랜 실행시간이 소요됩니다.
시간 복잡도는 O(N)입니다.
계수 정렬
import java.util.Arrays;
import java.util.Scanner;
public class CountingSort {
public static void countingSort(int[] arr) {
int n = arr.length;
// 최대값과 최소값 찾기
int max = arr[0];
int min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
// 최대값과 최소값의 범위에 해당하는 배열을 생성
int range = max - min + 1;
int[] count = new int[range];
// 배열에서 각 원소가 몇 번 등장하는지 세서 count 배열에 저장한다
for (int i = 0; i < n; i++) {
count[arr[i] - min]++;
}
// count 배열을 누적 합 배열로 변경
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 임시 배열
int[] sortedArr = new int[n];
// 기존 배열을 역순으로 스캔하면서 정렬
// arr[i]값의 인덱스를 찾아가는 과정
for (int i = n - 1; i >= 0; i--) {
int value = arr[i];
int index = count[value] - 1;
System.out.println(index);
sortedArr[index] = value;
count[value]--;
}
// 정렬된 결과를 원래 배열에 넣어줌
System.arraycopy(sortedArr, 0, arr, 0, n);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt()+1;
int[] arr = new int[n];
for(int i = 1; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(Arrays.toString(arr));
countingSort(arr);
System.out.println(Arrays.toString(arr));
}
}
기수 정렬
import java.util.Arrays;
import java.util.Scanner;
public class RadixSort {
public static void radixSort(int[] arr) {
int n = arr.length;
int max = getMax(arr);
// 가장 큰 자릿수까지 반복해서 정렬
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, n, exp);
}
}
// 최댓값 찾기
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
private static void countingSortByDigit(int[] arr, int n, int exp) {
int range = 10; // 0~9 까지
int[] count = new int[range]; // 임시 배열
int[] sortedArr = new int[n];
// 현재 자릿수에 해당하는 숫자
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 누적 합 배열
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
sortedArr[count[digit] - 1] = arr[i];
count[digit]--;
}
System.arraycopy(sortedArr, 0, arr, 0, n);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt()+1;
int[] arr = new int[n];
for(int i = 1; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(Arrays.toString(arr));
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
}
버킷 정렬
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class BucketSort {
public static void bucketSort(double[] arr) {
int n = arr.length;
int numOfBuckets = 10; // 버킷의 개수 임시 설정
// 버킷 담을 배열
ArrayList<Double>[] buckets = new ArrayList[numOfBuckets];
for (int i = 0; i < numOfBuckets; i++) {
buckets[i] = new ArrayList<>();
}
// 입력 배열의 원소들을 각 버킷에 넣는다
for (int i = 0; i < n; i++) {
int bucketIndex = (int) (arr[i] * numOfBuckets);
// 버킷 인덱스가 배열 범위를 벗어나지 않도록 보정
if (bucketIndex >= numOfBuckets) {
bucketIndex = numOfBuckets - 1;
}
buckets[bucketIndex].add(arr[i]);
}
// 각 버킷 정렬
for (int i = 0; i < numOfBuckets; i++) {
Collections.sort(buckets[i]);
}
// 정렬된 버킷 합치기
int index = 0;
for (int i = 0; i < numOfBuckets; i++) {
for (double element : buckets[i]) {
arr[index++] = element;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt();
double[] arr = new double[n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextDouble();
}
System.out.println(Arrays.toString(arr));
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
}
감사합니다 !