[Sort] radix sort (with counting sort)

문제

I : 정수를 요소로 갖는 배열 (arr1)

O : 오름차순으로 radix sort  (output)

---

Counting Sort

( 참고 링크 )

1. 입력받은 배열의 요소 중, 최대값을 구한다.

2. 최대값+1 길이의 배열을 새로 만든다. (arr2)

   (최대값과 같은 숫자의 인덱스까지 만들기 위함)

3. 입력받은 배열(arr1)을 순회하며, 요소와 같은 숫자인 인덱스에 해당하는 값이 나올때마다 +1

4. 새로만든 배열(arr2)에 각 인덱스 값을 배열로 만든다.

5. 이때, 각 인덱스에 해당하는 값의 갯수만큼 배열에 넣으면 된다.

 

예시) arr1은 최대값이 5이며 ; arr2.length = arr1.length +1 = 6이고 ; output.length = arr1.length다 

arr1

1

3

0

1

5

arr2의 index	0	1	2	3	4	5
arr2	1 1개 count됨	2 2개 count됨	0 0개 count됨	1 1개 count됨	0 0개 count됨	1 1개 count됨

output

0 =arr2의 0번인덱스

1 =arr2의 1번인덱스

1 =arr2의 1번인덱스

3 =arr2의 3번인덱스

5 =arr2의 5번인덱스

---

Radix Sort

( 참고링크 ) 

1. 길이가 10인 queue를 생성한다. (인덱스 값으로 치자면 0~9인거임)

2. 입력받은 배열 (arr1)을 대상으로 각 값의 1의 자리 수에 해당하는 값의 순서대로 queue에 넣는다

3. 입력받은 배열 (arr1)을 대상으로 각 값의 10의 자리 수에 해당하는 값의 순서대로 queue에 넣는다

4. 2~3번과 같은 수순으로 최대자리수 까지 반복하며 queue에 넣고 빼고를 반복한다.

   즉, 1의자리 수부터 순차적으로 비교하며 정렬을 하는 방법이다.

 

---

코드

내가 푼 코드

import java.util.*;

public class radixSort {
    public static void main(String[] args) {
        int[] output = radixSort(new int[]{3, 1, 21});
        System.out.println(Arrays.toString(output));
    }


    public static int[] radixSort(int[] arr) {
      /* TODO:
    1. counting sort로 배열생성 및 sort
    2. counting sort에 따른 인자를 queue에 집어넣음
    3. queue에 넣은 숫자를 차례로 Array에 대입 및 리턴
    */
        //max값 구하기
        int max = 0;
        for (int i=0 ; i<arr.length ; i++) {
            if(arr[i]>=max) max = arr[i];
        }

        // max+1 길이의 새 배열 만들어서 count
        int [] arr2 = new int[max+1];
        for(int j=0 ; j<arr.length ; j++) {
            arr2[arr[j]] += 1;
        }

        // arr2에 분류해놓은 인덱스 값을 queue에 순차적으로 저장
        Queue<Integer> que = new LinkedList<>();
        for (int k=0 ; k<arr2.length ; k++) {
            Integer temp = k;
            if(arr2[k]!=0) {
                for(int l=1 ; l<=arr2[k] ; l++) {
                    que.add(temp);
                }
            }
        }

        // queue에 저장한 인덱스당 갯수만큼 array에 추가d
        int[] output = new int[que.size()];
        for(int m=0 ; m<arr.length; m++) {
            output[m] = que.poll();
        }

        return output;
    }
}

 

레퍼런스 코드

깃 링크 참고 : 깃 링크