기수 정렬 (진행중)

1. 개요

• 기수정렬은 비교 연산을 하지 않으며 각 숫자를 해당 숫자 번째 배열에 넣고 넣은 순서대로 꺼내면 정렬이 되는 정렬이다.

• 정렬 속도가 빠르다

• 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다

• 자료구조 - Bucket(Que)

• 시간 복잡도 - O(dn)

정렬방식

1. 0~9 까지의 버킷을 준비한다.

2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 버킷에 차례대로 데이터를 둔다.
   

3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다.

4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2,3번 과정 반복

point

• 배열 10개로 충분히 정렬을 할 수 있다.
• 퀵 소트 보다 빠르다
• 자연수만 가능하다 - 배열엔 -값을 가진 인덱스가 없기 때문

2. 구현

---

💻 Before

public class RadixSort {
   public static void main(String[] args) {
       int[] arr = new int[]{7, 4, 5, 9, 1, 0};

       // 10개 생성
       int[] redixArr = new int[10];
       Arrays.fill(redixArr, -1); // -1로 채우기

       // 배열에서 꺼내서 넣기
       for (var i : arr) {
           redixArr[i] = i;
       }

       System.out.println(Arrays.toString(redixArr));
      
       // 1개씩 꺼내서 arr에 다시 넣기
       int cnt = 0;
       for (int i = 0; i < redixArr.length; i++) {
           if(redixArr[i] != -1) {
               arr[cnt++] = redixArr[i];
           }
       }
       System.out.println(Arrays.toString(arr));
   }
}

🔽 결과 

[0, 1, -1, -1, 4, 5, -1, 7, -1, 9] 

[0, 1, 4, 5, 7, 9] // 정렬된 값이 성공적으로 나왔다. 

본 코드는 0~10범위의 숫자만이 의도한 정렬값이 나오고, 범위에 넘어간 수가 input되면 에러가 난다.
그렇다고 input될 숫자의 범위를 넓게 하여 배열의 수를 크게 잡으면 메모리 문제가 생길 것이다.
기수정렬은 1의 자리로 정렬했다가 10의 자리로 정렬,,, input되는 가장 큰 자릿수로의 정렬을 하며 배열 10개 짜리 하나로 효율적인 정렬을한다.

💻 After

1. 일의 자리 기준으로 정렬하기

Deque란?
: Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미한다.
new Deque()로 선언이 안되며, 대신 new ArrayDeque(), new LinkedList() 등으로 선언한다.