본문 바로가기
Algorithm

Radix Sort

by orioncsy 2022. 10. 11.
import java.util.*;

public class Solution { 
	public int[] radixSort(int[] arr) {
		// TODO:
		//정렬할 최대 값을 구하기
		//10개 배열 큐를 선언
		//일의 자리수 부터 최대 자릿수까지 반복해서 큐에 넣고 빼서 배열에 넣기
		int max=arr[0];
		for(int i=0; i<arr.length; i++)
			if(max<arr[i]) max=arr[i];
		Queue<Integer>[] bucket=new LinkedList[10];
		for(int i=0; i<bucket.length; i++) bucket[i]=new LinkedList<>();

		for(int digit=1; digit<=max; digit*=10){
			for(int i=0; i<arr.length;i++){
				bucket[(arr[i]/digit)%10].add(arr[i]);
			}
			int j=0;
			for(int i=0; i<bucket.length; i++){
				while(!bucket[i].isEmpty()){
					arr[j++]=bucket[i].peek();
					bucket[i].poll();
				}
			}
		}
		return arr;
	} 
}

'Algorithm' 카테고리의 다른 글

Heap Sort  (0) 2022.10.11
Merge Sort  (0) 2022.10.11
Insertion sort  (1) 2022.10.07
Bubble Sort  (0) 2022.10.06
Quick Sort  (0) 2022.10.06