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

계수 정렬이란 ? 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행함

과정 : 

1. 배열을 쭉 돌면서 해당 값을 index로 하는 새로운 배열의 값을 1 증가시킨다.

array[0] = 1 → counting[1]값 1증가

array[1] = 3 → counting[3]값 1증가

…

counting배열은 1의 개수는 3개, 2의 개수는 1개, … 등 해당 인덱스 값의 개수를 담는 배열이다.

2. 완성된 counting 배열의 누적합을 계산한다.

counting[1] → counting[0] + counting[1]

counting[2] → counting[1] + counting[2]

…

counting[5] → counting[4] + counting[5]

3. 최종 정렬하기

counting 배열은 시작값을 알려주기 때문에 해당 값을 counting 배열의 값을 보고 넣어주면 된다.

array[9] = 1, counting[1] = 3 으로 counting 배열의 값에서 1을 빼주고 새로운 result 배열에 넣어주면 된다. result 배열에 넣어준 후에는 다음 값을 위해서 counting 배열의 값을 -1 해주어야 한다.

package Sort;

public class CountingSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] array = new int[30];
		int[] counting = new int[10];
		int[] result = new int[30];

		// 랜덤값 생성하기 (0 ~ 9)
		for (int i = 0; i < array.length; i++) {
			array[i] = (int) (Math.random() * 10);
		}

		// 1번과정
		for (int i = 0; i < array.length; i++) {
			counting[array[i]]++;
		}

		// 2번과정
		for (int i = 1; i < counting.length; i++) {
			counting[i] = counting[i] + counting[i - 1];
		}

		// 3번과정
		for (int i = array.length - 1; i >= 0; i--) {
			int value = array[i];
			counting[value]--;
			result[counting[value]] = value;

		}
		// 결과 출력
		System.out.println("정렬된 결과:");
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}

}

기수 정렬이란 ? 원소들이 모두 상수 k개 이하의 자릿수를 가진 자연수와 같은 특수한 경우에 사용할 수 있는 방법

예를들어, {28, 93, 39, 81, 62, 72, 38, 26}로 구성된 배열이 있다.

먼저 1의 자릿수로 정렬을 하게 되면 {81, 62, 72, 93, 26, 28, 38, 39}로 정렬이 될 것이다. 이제 10의 자릿수로 정렬을 하게 되면 {26, 28, 38, 39, 62, 72, 81, 93}으로 배열의 원소들이 정렬된 것을 확인할 수 있다.

package Sort;

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

public class RadixSort {

	static final int bucketSize = 10;
	
	public static void main(String[] args) {
		int[] arr = {28, 93, 39, 81, 62, 72, 38, 26};
		
		radix_Sort(arr.length, arr);
		
		for (int i = 0; i < arr.length; ++i) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void radix_Sort(int n, int[] arr) {
		//bucket 초기화
		Queue<Integer>[] bucket = new LinkedList[bucketSize];
		for (int i = 0; i < bucketSize; ++i) {
			bucket[i] = new LinkedList<>();
		}
		
		int factor = 1;
		
		//정렬할 자릿수의 크기 만큼 반복한다.
		for (int d = 0; d < 2; ++d) {
			for (int i = 0; i < n; ++i) {
				bucket[(arr[i] / factor) % 10].add(arr[i]);
			}
			
			for (int i = 0, j = 0; i < bucketSize; ++i) {
				while (!bucket[i].isEmpty()) {
					arr[j++] = bucket[i].poll();
				}
			}
			
			factor *= 10;
		}
	}
}

3. 버킷 정렬이란 ? 정렬하고자 하는 원소들이 균등 분포 할때를 가정한 유용한 정렬 알고리즘

과정 : 

1. N=10(배열의 인덱스가 정수 0-9까지 필요로함)인 빈 버킷 또는 리스트 B를 생성힌다.

2. 배열 A의 모든 원소 A[i] 에 대해  B[N*A[i]] 버킷에 A[i]를 추가한다.

ex) A[0] = 0.78 -> B[10*0.78 = 7] = 0.78 ...

3. B[N*A[i]] 버킷에 A[i]를 추가시 삽입정렬(insertion sort)을 사용하여 각 버킷에 추가된 자료를 정렬한다.

4. 모든 버킷들 (B[0] 부터 B[N-1])에 정렬된데이터를 순차적으로 연결한다.

package Sort;

import java.util.ArrayList;
import java.util.List;

public class BucketSort {

    public static void main(String[] args) {
        // 입력 데이터 배열
        float[] datasets = { 0.897f, 0.156f, 0.565f, 0.556f, 0.656f, 0.1234f, 0.665f, 0.3434f };

        // 버킷 정렬 수행
        bucketSort(datasets);

        // 정렬된 결과 출력
        for (int i = 0; i < datasets.length; i++) {
            System.out.print(datasets[i] + " ");
        }
    }

    public static void bucketSort(float[] datasets) {
        // 0-9까지 버킷 리스트 생성
        List<Float>[] buckets = new ArrayList[10];
        for (int i = 0; i < datasets.length; i++) {
            int index = (int) (datasets[i] * 10); // 0.0~0.9의 값은 0-9의 버킷에 할당
            if (buckets[index] == null) {
                buckets[index] = new ArrayList<>();
            }

            // 맨 뒤에 값을 추가하고 삽입 정렬 수행
            buckets[index].add(datasets[i]);
            insertionSort(buckets[index], datasets[i]);
        }

        int c = 0;
        // 버킷들을 합치면서 최종 정렬된 배열로 복사
        for (int i = 0; i < 10; i++) {
            if (buckets[i] != null) {
                int size = buckets[i].size();
                for (int j = 0; j < size; j++) {
                    datasets[c++] = buckets[i].get(j);
                }
            }
        }
    }

    // 버킷 내에서 삽입 정렬 수행
    public static void insertionSort(List<Float> list, float v2) {
        int bucketSize = list.size() - 1;
        int i = 0;
        for (i = bucketSize - 2; i >= 0; i--) {
            float v1 = list.get(i);
            if (list.get(i) < v2)
                break;
            list.set(i + 1, v1);
        }

        if (i >= 0) {
            list.set(i, v2);
        }
    }
}