정렬에 관한 정리-2

https://pro-gramm-ing.tistory.com/488

정렬에 관한 정리 - 1

앞서 비교 기반 정렬을 살펴 보았다. 이번에는 비비교 기반 정렬을 알아보고자 한다. 직관적이거나 만들기 쉽지는 않지만 비교적 실행속도가 빠르고 효율적이다.

 

비비교 기반 정렬

1. 계산 정렬(Counting Sort)

이 정렬방식은 값을 인덱스와 매핑을 다시 시킨 후 정렬을 하는 방식이다. 계산 정렬은 다음과 같은 상황에서 사용이 가능하다. 

- 1.배열에 중복적인 요소들이 있는경우

   ex) [0,0,1,3,5] : 0은 중복된 요소이다.

- 2.정의된 값 범위 밖의 요소들을 가진 경우

  ex) [0,1,3,5] : 배열의 크기는 4이지만 크기 밖의 요소 5를 가진다.

- 3.숫자가 아니더라도 순서가 있는 문자도 가능

  ex) ['a','b','c'] : 문자로 된 배열도 정렬이 가능하다.

---

1번째 단계

이런 배열이 있다고 해보자, 이 배열의 이름을 A라고 하자.

index	0	1	2	3	4	5	6
value	5	4	5	5	1	1	3

그리고 이런 비어있는 배열이 있다고 해보자. 얘는 B이다. B의 크기는 A의 값들중 최대값+1 의 크기를 가진다.

index	0	1	2	3	4	5
value	0	0	0	0	0	0

---

2번째 단계

A[0]의  값은 5이다. 그럼 B[ A[0] ]의 값을 1 더한다. 즉,  B[5] 에 숫자를 1증가시키자.

index	0	1	2	3	4	5
value	0	0	0	0	0	1

 

A[1]의  값은 4이다. 그럼 B[ A[1] ]의 값을 1 더한다. 즉,  B[4] 에 숫자를 1증가시키자.

index	0	1	2	3	4	5
value	0	0	0	0	1	1

 

A[2]의  값은 또 5이다. 그럼 B[ A[5] ]의 값을 1 더한다. 즉,  B[5] 에 숫자를 1증가시키자.

index	0	1	2	3	4	5
value	0	0	0	0	1	2

 

이런식으로 A[마지막 index] 까지 B에 증가시키는 과정을 거치면 다음과 같은 B가 만들어진다.

index	0	1	2	3	4	5
value	0	2	0	1	1	3

 

---

3번째 단계

이 계산 정렬의 중요 원칙은 0부터 배열가능한 최대값(이 예시에서는 A배열의 최대값 5) 까지 정렬할수 있다고 가정하고, 배열할 요소들의 빈도를 추적하는 것이다. 위의 예시에서 정렬되어야 하는 형태는 결국 아래와 같을텐데

index	0	1	2	3	4	5	6
value	1	1	3	4	5	5	5

생각해보면, 1이 두번 나오고, 3과 4가 각각 한번 나오고 5가 세번 나오게 하면 되는것이다. 이를 위해서는 단계가 하나 더 필요한데 배열을 하나 더 만들자. 얘는 C이다. 0부터 최대값(여기선 5)을 정렬하는데 현재 A에는 0이 없다. 0인덱스에 0을 넣자.

index	0	1	2	3	4	5
value	0

 

그리고 다음요소는 B배열에서 이전요소와 현재요소의 총합이 오도록 배열을 초기화 하자.

index	0	1	2	3	4	5
value	0	2	0	1	1	3

index	0	1	2	3	4	5
value	0	0 + 0 = 0	0 + 2 = 2	2 + 0 = 2	2 + 1 = 3	3 + 1 = 4
과정	0	B[0] + 0(최소값)	B[0] + B[1]	B[1] + B[2]	B[2] + B[3]	B[3] + B[4]

 

이제 C를 참고해서 정렬을 해보자.

index	0	1	2	3	4	5	6
value	5	4	5	5	1	1	3

A의 첫번째 요소는 5이다. C[ A[0] ] 의 값은 4이다. 정렬을 위한 인덱스 4에 5를 넣자 

index	0	1	2	3	4	5	6
value					5

 

그리고 C[ A[0] ] 에 1을 더해주자, 이는 중복된 값을 정렬 위해서이다. 

index	0	1	2	3	4	5
value	0	0	2	2	3	5

 

그리고 이와같은 과정을 반복한다. A의 두번째 요소는 4이다. C[ A[4] ] 는 3이니 3번째 인덱스에 4를 배치하자.

index	0	1	2	3	4	5	6
value				4	5

그리고 마찬가지로 C[3]의 값에 +1을 한다.

index	0	1	2	3	4	5
value	0	0	2	2	4	5

 

A[2]의 경우, C[ A[2] ] = 5, 5번째 인덱스에 정렬

index	0	1	2	3	4	5	6
value				4	5	5

C[ A[2] ] 에 1을 또 더한다.

index	0	1	2	3	4	5
value	0	0	2	2	4	6

A[3]의 경우, C[ A[3] ] = 5, 5번째 인덱스에 정렬

index	0	1	2	3	4	5	6
value				4	5	5	5

C[ A[3] ] 에 1을 또 더한다.

index	0	1	2	3	4	5
value	0	0	2	2	4	7

A[4]의 경우 A[4]의 값은 1, C[ A[4] ] = 0, 0번째 인덱스에 정렬

index	0	1	2	3	4	5	6
value	1			4	5	5	5

C[ A[4] ] 에 1을 또 더한다.

index	0	1	2	3	4	5
value	0	1	2	2	4	7

A[5]의 경우 A[5]의 값은 1, C[ A[5] ] = 1, 1번째 인덱스에 정렬

index	0	1	2	3	4	5	6
value	1	1		4	5	5	5

C[ A[5] ] 에 1을 또 더한다.

index	0	1	2	3	4	5
value	0	2	2	2	4	7

A[6]의 경우 A[6]의 값은 3, C[ A[6] ] = 2, 2번째 인덱스에 정렬

index	0	1	2	3	4	5	6
value	1	1	3	4	5	5	5

이미 정렬은 되었지만 로직상 C[ A[6] ] 에 1을 또 더한다.

index	0	1	2	3	4	5
value	0	1	2	3	4	7

 

코드의 예시는 다음과 같다.

public class Solution {
    public void countingSort(int[] arr) {
        int K = Arrays.stream(arr).max().getAsInt();
        int[] counts = new int[K + 1];
        for (int elem : arr) {
            counts[elem] += 1;
        }
        int startingIndex = 0;
        for (int i = 0; i < K + 1; i++) {
            int count = counts[i];
            counts[i] = startingIndex;
            startingIndex += count;
        }

        int sortedArray[] = new int[arr.length];
        for (int elem : arr) {
            sortedArray[counts[elem]] = elem;
            counts[elem] += 1;
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = sortedArray[i];
        }
    }
}

계산정렬의 시간복잡도는 O( N + K) 이다. 새로운 배열의 초기화에 N의 시간이 걸리고 최대값인 K만큼의 시간이 추가로 걸린다. 이 계산정렬의 한계는 고정된 크기의 배열에 적용할 수 있다는 것이다.  또 다른 비교 기반 정렬보다 빠를 수는 있지만, K의 범위가 N에 비해 큰 경우에는 오히려 느린 정렬보다도 더 나쁜 성능을 발휘할 수도 있어 주의가 필요하다.

---

2.기수정렬(Radix Sort)

계산 정렬은 제한된 범위에서 정렬을 해야된다. 또 배열의 최대값이 크다면 불필요한 메모리가 소모될 수도 있다. 이런 상황을 해결하기 위해 계산 정렬에서 확장된 정렬이 기수정렬이다. 기수정렬은 문자열및 컬렉션, 정수 컬렉션에 잘 작동된다.

기수정렬에는 몇가지 변형이 있지만 이번 글은 LSD( Least Significant Digit 즉, 최하위 숫자) 에 중점을 두고자 한다. 

다음과 같은 배열 A가 있다고 하자.

index	0	1	2	3	4	5	6	7
value	889	2448	4021	4500	6270	7324	8192	9011

이 배열을 다음과 같이 바꿔볼 수 있다. 이 바꾼 형태를 W라고 해보자

0	8	8	9
2	4	4	8
4	0	2	1
4	5	0	0
6	2	7	0
7	3	2	4
8	1	9	2
9	0	1	1

W의 최대 정수의 자리수를 구한 다음 최소단위, 즉 1의 자리에서부터 계산정렬을 하는것이다. 그럼 1의 자리에서 실행한다면 w는 다음과 같을 것이다. 

4	5	0	0
6	2	7	0
4	0	2	1
9	0	1	1
8	1	9	2
7	3	2	4
2	4	4	8
0	8	8	9

차례대로 10의 자리, 100의 자리, 1000의 자리까지 정렬을 하면 정렬이 완성되게 된다. 

0	8	8	9
2	4	4	8
4	0	2	1
4	5	0	0
6	2	7	0
7	3	2	4
8	1	9	2
9	0	1	1

 

구현 코드는 다음과 같다.

public class Solution {
    private static final int NUM_DIGITS = 10;

    public void countingSort(int[] arr, int placeVal) {
        int[] counts = new int[NUM_DIGITS];

        for (int elem : arr) {
            int current = elem / placeVal;
            counts[current % NUM_DIGITS] += 1
        }

        int startingIndex = 0;
        for (int i = 0; i < counts.length; i++) {
            int count = counts[i];
            counts[i] = startingIndex;
            startingIndex += count;
        }

        int[] sortedArray = new int[arr.length];
        for (int elem : arr) {
            int current = elem / placeVal;
            sortedArray[counts[current % NUM_DIGITS]] = elem;
         
            counts[current % NUM_DIGITS] += 1;
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sortedArray[i];
        }
    }

    public void radixSort(int[] arr) {
        int maxElem = Integer.MIN_VALUE;
        for (int elem : arr) {
            if (elem > maxElem) {
                maxElem = elem;
            }
        }

        int placeVal = 1;
        while (maxElem / placeVal > 0) {
            countingSort(arr, placeVal);
            placeVal *= 10;
        }
    }
}

기수정렬에는 몇가지 매개변수가 필요하다. 1. 정수 목록 내 최대 숫자 길이(W), 원래 입력정수 배열의 크기(N), 그리고 계산 정렬을 하기 위한 알파벳(K)(정수가 아닐때, 정수라면 10진수니 10을 쓰면 된다.)을 알아야 한다. 기수정렬은 안정적인 정렬이며, O( W( N + K ) ) 의 시간복잡도를 가진다. 

계산 정렬보다 훨씬 빠르지만 메모리를 더 필요로 한다. 최상위 숫자를 먼저 살펴보는 MSD 기수 정렬은 구현이 까다롭지만 LSD 기수 정렬보다 평균적으로 더 나은 성능을 낸다고 한다.

---

3.버킷정렬

다음과 같은 배열 A가 있다고 가정해보자

A = [22,50,32,28,41,12]

그리도 5개의 버킷(저장소) 이 있다고 가정해보자. 5개의 버킷은 10의 단위로 저장할 수 있다고 생각해보자. 그리고 그 버킷에 A의 요소 순서대로 저장을 해보자

1버킷(0~9)
2버킷(10~19)	12
3버킷(20~29)	22	28
4버킷 (30~39)	32
5버킷 (40~50)	50	41

 

그리고 계산정렬이나 다른 정렬을 사용해서 버킷들 안에 있는 요소들을 정렬하면 된다.

1버킷(0~9)
2버킷(10~19)	12
3버킷(20~29)	22	28
4버킷 (30~39)	32
5버킷 (40~50)	41	50

코드로 구현하면 다음과 같다.

import java.util.*;

public class Solution {
    public void bucketSort(int[] arr, int K) {
        List<List<Integer>> buckets = new ArrayList<ArrayList<Integer>>(K);
        int shift = Arrays.stream(arr).min().getAsInt();
        int maxValue = Arrays.stream(arr).max().getAsInt() - shft;

        double bucketSize = (double) maxValue / K;
        if (bucketSize < 1) {
            bucketSize = 1.0;
        }
        for (int elem : arr) {
            int index = (int) (elem - shift) / bucketSize;
            if (index == K) {
                // put the max value in the last bucket
                buckets[K - 1].add(elem);
            } else {
                buckets[index].add(elem);
            }
        }

        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        List<Integer> sortedList = new ArrayList<Integer>();
        for (List<Integer> bucket : buckets) {
            sortedList.addAll(bucket);
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = sortedList.get(i);
        }
    }
}

버킷 정렬의 시간복잡도는 최악의 경우 O(N²) 이다. 일반적으로 버킷에 있는 요소들을 정렬시 사용되는 알고리즘은 삽입정렬이다. 버킷이 전체 목록에 비해 너무 많은 요소를 가지지 않는 경우가 대부분이기 때문이다. 최악의 경우가 아닌 이상 평균적으로는 O(버킷에 있는 요소의 개수 + 버킷개수)의 시간복잡도를 가진다.

---

추가적으로 각 정렬의 시간복잡도와 공간복잡도, 안정적인 정렬여부에 대한 정리를 한 표이다.