Counting, Radix, Bucket Sorting

이번 Posting에서는 Counting sort, Radix sort, Bucket sort에 대해서 정리를 할 것이다.

Counting sort

배열 내에 최댓값을 배열의 길이만큼의 새로운 버킷을 만든다.
배열의 각 값들을 인덱스로하는 버킷 배열에 그 수를 counting.
counting이 완료된 것을 작은 index부터 큰 쪽으로 누적 시킨다.
원래 배열 뒤에서부터 차례로 자리를 찾는다.
자리는 bucket에 저장된 값으로 넣어준 후 하나씩 감소시켜 같은 값이 있는 경우를 계산한다.
낮은 인덱스부터 출력을 하면 정렬된 결과를 얻을 수 있음.

코드는 다음과 같다.

public class CountingSort {
    static int[] arr = {7, 3, 5, 9, 11, 2, 6, 12, 10};
    static int[] sorted;
    static int[] bucket;
    static int max = 0;
    public static void main(String[] args) {
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        for (int i = 1; i < bucket.length; i++) {
            bucket[i] += bucket[i - 1];
        }
        sorted = new int[arr.length];
        for (int i = arr.length - 1; i > -1; i--) {
            sorted[--bucket[arr[i]]] = arr[i];
        }
        for(int i = 0; i < sorted.length; i++) {
            System.out.print(sorted[i] + " ");
        }
    }
}

Radix sort

기수 정렬은 분배 방식의 정렬 방법으로 정렬할 원소의 키 값에 해당하는 버킷의 원소를 분해하고 버킷의 순서대로 원소를 꺼내는 방법을 반복해서 정렬하는 방법이다.

우선적으로 일의자리로 걸러내어 큐에 집어 넣는다. 그렇게 하여 임시 배열에 차례로 집어넣는다.

이후 십의자리로 걸러내어 큐에 집어 넣는다. 또한 임시 배열에 차례로 집어넣는다.

코드는 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;

public class RadixSort {
    static int[] arr = {24, 21, 66, 32, 12, 55, 44, 42, 63, 52, 32};
    static int factor, max, count, index;
    static Queue<Integer>[] queue = new LinkedList[10];
    public static void main(String[] args) {
        factor = 1; max = 0; count = 1; index = 0;
        for (int i = 0; i < 10; i++) {
            queue[i] = new LinkedList<>();
        }
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        while (max / factor > 0) {
            for (int i = 0; i < arr.length; i++) {
                index = (arr[i] / factor) % 10;
                queue[index].add(arr[i]);
            }
            index = 0;
            for (int i = 0; i < 10; i++) {
                while (!queue[i].isEmpty()) {
                    arr[index++] = queue[i].poll();
                }
            }
            factor *= 10;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

Bucket sort

구간의 크기가 0.1인 10개의 버킷이 있다고 하자
어떤 배열의 원소 값에 따라 적절한 버킷에 삽입하고 같은 버킷에 들어간다면 연결리스트로 연결시켜 놓는다.
각 버킷리스트에 대하여 insertion sorting을 행한다.

이 블로그 검색

Do.

Counting, Radix, Bucket Sorting

이 블로그의 인기 게시물

웹툰 무료로 볼 수 있는 사이트

BackJoon 1011, Fly me to the alpha centauri, 규칙 찾기 문제

BaekJoon 6591, 이항 쇼다운 조합문제