알고리즘

[알고리즘] 자료구조 - 특수 정렬 ( 계수 정렬, 기수 정렬, 버킷 정렬 )

menus 2023. 7. 17. 00:54
728x90

이번 글에서는 정렬 중 특수 정렬에 대해서 정리해보겠습니다 !

 

( 지난 기본 정렬, 고급 정렬에 이어 특수 정렬도 오름차순을 기준으로 설명하겠습니다. )

 

특수 정렬인 계수 정렬, 기수 정렬, 버킷 정렬에 대한 개념 정리를 하고 예시 코드도 설명하도록 하겠습니다.

 


 

계수 정렬 ( 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));
    }
}

 

감사합니다 !