Java - 정렬 알고리즘 - 9 (기수 정렬)

◎기수 정렬

가장 작은 자릿수부터 가장 큰 자릿수까지 자릿수(기수) 별로 자리를 찾아주는 방식으로 숫자를 정렬하는 방식

---

◎기수 정렬의 특징

1.  비교 정렬(comparison sort)이 아니다

 기수 정렬은 데이터를 비교하면서 찾지 않는다.

 

2. 제자리 정렬(in-place sort)이 아니다

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다.

 

3. 안정 정렬(unstable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다.

---

◎기수 정렬의 동작

기수 정렬은 모든 데이터의 길이가 같아야 사용할 수 있다.

ex. [aaa,bbb,dsd,gdf,ret] => 모든 데이터의 길이가 3이므로 기수정렬 사용가능

 

 

1. 0~9번까지의 Queue를 생성한다

2. 모든 데이터를 가장 작은 자릿수를 기준으로 Queue에 넣는다.

(ex. '235'이면 가장 작은 자릿수가 5이므로 5번 Queue에 '235'를 넣는다.)

3. 0번 Queue부터 데이터를 다시 가져온다.

4. 모든 데이터를 그 다음 자릿수를 기준으로 Queue에 넣는다.

(ex. '235'이면 그 다음 자릿수가 3이므로 3번 Queue에 '235'를 넣는다.)

5. 0번 Queue부터 데이터를 다시 가져온다.

6.  데이터의 길이만큼 반복..

 

1의 자리 수를 기준으로 Queue에 입력, 출처: https://lktprogrammer.tistory.com/48

0번  Queue부터 데이터를 다시 가져온다.

10의 자리 수를 기준으로 Queue에 입력

0번  Queue부터 데이터를 다시 가져온다., 데이터의 길이만큼 반복했으므로 정렬 완료!

---

◎기수 정렬의 구현

package SortAlgorithm;

import java.util.Queue;
import java.util.LinkedList;
import java.lang.Math;

	//기수 정렬
	private void radixsort(int[] numarr, int data_length) {
		
		//0~9번의 Queue 생성
		Queue<Integer>[] queues= new Queue[10]; 
		for(int i = 0; i<queues.length; i++) {
			queues[i] = new LinkedList<>();
		}
		
		//데이터의 길이만큼 반복
		while(data_length != 0) {
			for(int i = 0; i<numarr.length; i++) {
				//자릿수에 해당하는 수 구하기
				int digit = (numarr[i]%(int)Math.pow(10,data_length))/(int)Math.pow(10,data_length-1); 
				//자릿수에 해당하는 수를 기준으로 알맞은 번호의 queue에 넣기
				queues[digit].add( numarr[i]); 
			}
			int i, p;
			//0번  Queue 부터 원소 꺼내기
			for(i = 0, p =0; i<numarr.length; i++) {
				while(!queues[i].isEmpty()) {
					numarr[p++] =queues[i].poll();
				}
			}
			data_length--;
		}
		
		print(numarr, "기수 정렬");
		
	}
    	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 1, 3, 4, 2, 6 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.radixsort(numarr,1);

	}
}

    

 

실행 결과:

원래 배열:[5, 1, 3, 4, 2, 6]
기수 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

◎기수정렬의 시간복잡도

기수정렬의 시간복잡도는 O(dn)이다. (d는 데이터의 길이, n은 배열의 길이)

특정한 조건을 만족할 때에는 매우 강력한 알고리즘이지만, 범용성이 크게 부족하다는 단점이 있다

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처:    https://st-lab.tistory.com/195

◆기수 정렬의 시간복잡도는 O(dn)이고, 계수정렬의 시간복잡도가 O(n+k)이다.◆

 

 

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm

jerry-ryu/java_problemsolving_algorithm