📚 Radix Sort

Radix Sort(기수 정렬) 이란 배열이 모두 같은 자릿수의 정수로 이루어져있을 때, 각 자리수를 비교해서 정렬하여 최종적으로 모든 자릿수가 정렬되도록 하는 방법이다.

개념은 0부터 9까지 각 자릿수를 담을 큐의 배열을 만들고, 각각의 큐에 해당 자릿수에 맞는 요소를 enqueue해주면 된다.
그리고 마지막에 배열을 순회하며 dequeue하게 되면 한 자릿수에 대해 정렬되어 있는 배열이 탄생하게 된다. 이를 자릿수만큼 반복하면 모두 정렬된다.

💻 Implementation

기수 정렬은 MSD(Most Significant Digit first)와 LSD(Least Significant Digit first) 로 갈릴 수 있다.

MSD

MSD는 큰 자릿수부터 비교를 한다. 중간에 정렬이 완료될 수 있다는 장점이 있지만 정렬까지만 해보는 것이 목표이므로 우선 구현만 해보겠다.

class LSD {
	public static void main(String[] args) {
		int[] arr = {82, 34, 51, 65, 16, 27, 19};
		int d, n, r;

		d = 2;
		n = 7;
		r = 10;
		LSDSort(arr, d, n, r);
		for(int i=0;i<7;i++)System.out.print(arr[i]+ " ");
	}

	public static void LSDSort(int arr[], int d, int n, int r) {
		Queue[] bins = new Queue[r];
		for (int i=0;i<r;i++)
			bins[i] = new Queue();
		int digit = 1;
		for (;d>0; d--) {
			int j = 0;
			for (int i=0;i<n;i++) {
				if (digit == 1)
					bins[(arr[i] % 10)].enqueue(arr[i]);
				else
					bins[(arr[i] / digit)].enqueue(arr[i]);
			}
			for (int i=0;i<10;i++)
				while (bins[i].isEmpty() == false)
					arr[j++] = bins[i].dequeue();
			digit *= 10;
		}
	}
}

LSD

LSD는 작은 자릿수부터 비교한다.

class LSD {
	public static void main(String[] args) {
		int[] arr = {82, 34, 51, 65, 16, 27, 19};
		int d, n, r;

		d = 2;
		n = 7;
		r = 10;
		LSDSort(arr, d, n, r);
		for(int i=0;i<7;i++)System.out.print(arr[i]+ " ");
	}

	public static void LSDSort(int arr[], int d, int n, int r) {
		Queue[] bins = new Queue[r];
		for (int i=0;i<r;i++)
			bins[i] = new Queue();
		int digit = 1;
		for (;d>0; d--) {
			int j = 0;
			for (int i=0;i<n;i++) {
				if (digit == 1)
					bins[(arr[i] % 10)].enqueue(arr[i]);
				else
					bins[(arr[i] / digit)].enqueue(arr[i]);
			}
			for (int i=0;i<10;i++)
				while (bins[i].isEmpty() == false)
					arr[j++] = bins[i].dequeue();
			digit *= 10;
		}
	}
}

⌛️ Time Complexity

MSD와 LSD 모두 시간복잡도는 O[d(n+r)] 이 된다.
d는 숫자의 자릿수, n은 배열의 요소 개수, r은 기수 (베이스, 진수) 이다.
자릿수를 알고 있을 때 주로 사용하므로 복잡도가 그리 높지 않을 것! 효과적인 정렬 방식이라고 한다.