기수 정렬은 값을 비교하지 않는 특이한 정렬입니다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다.
기수 정렬의 시간 복잡도는 O(kn)이고, k는 데이터의 자릿수를 의미합니다.
정렬 과정
입력한 수열은 몇 개의 키로 분류됩니다. 3자리이하 수라고 한다면, 1의 자리, 10의 자리, 100의 자리로 나누어 분류됩니다.
170, 45, 75, 90, 2, 24, 802, 66
1의 자리만 보고 정렬을 수행
↓
170, 90, 2, 802, 24, 45, 75, 66
10의 자리만 보고 정렬 수행
↓
2, 802, 24, 45, 66, 170, 75, 90
100의 자리만 보고 정렬 수행
↓
2, 24, 45, 66, 75, 90, 170, 802
위와 같은 과정을 통해 정렬이 됩니다.
소스 코드
// Radix Sort in Java Programming
import java.util.Arrays;
class RadixSort {
// Using counting sort to sort the elements in the basis of significant places
void countingSort(int array[], int size, int place) {
int[] output = new int[size + 1];
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max)
max = array[i];
}
int[] count = new int[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
// Calculate count of elements
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
// Calculate cumulative count
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// Function to get the largest element from an array
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
// Main function to implement radix sort
void radixSort(int array[], int size) {
// Get maximum element
int max = getMax(array, size);
// Apply counting sort to sort elements based on place value.
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// Driver code
public static void main(String args[]) {
int[] data = { 121, 432, 564, 23, 1, 45, 788 };
int size = data.length;
RadixSort rs = new RadixSort();
rs.radixSort(data, size);
System.out.println(Arrays.toString(data));
}
}
'Algorithm > 이론' 카테고리의 다른 글
인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) - JAVA (0) | 2023.05.18 |
---|---|
깊이 우선 탐색 (DFS : Depth First Search) - JAVA (0) | 2023.05.18 |
병합 정렬 (Merge Sort) - JAVA (0) | 2023.05.17 |
퀵 정렬 (Quick Sort) - JAVA (0) | 2023.05.17 |
삽입 정렬 (Insertion Sort) - JAVA (0) | 2023.05.17 |