[Sort] 기수 정렬(radix sort)
기수(radix) 정렬
-
어떤 기수 r을 이용하여 정렬 키를 몇 개의 숫자로 분해
- r=10 : 키를 십진수로 분할
- r=2 : 키를 이진수로 분할
-
기수-r 정렬에서는 r개의 빈(bin)이 필요
- 정렬되어야 하는 레코드가 R1,,,Rn일 때, 레코드의 키는 기수-r을 이용하여 분할 -> 0~(r-1) 사이의 d자리 키가 된다
- 각 빈의 레코드는 빈의 첫 레코드를 가리키는 포인터와 마지막 레코드를 가리키는 포인터를 통해 체인으로 연결되며, 체인은 큐처럼 동작
-
기수 정렬은 정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않음
-
정렬 대상의 모든 길이가 동일해야 가장 효율적
※ 좋은 예) [123, 486, 309, 944], [blue, rice, pain, book] 등등
※ 나쁜 예) [5643, -43, 1, 87912], [sky, pencil, water, a] 등등
-
길이가 각각 다를경우 빈 공간을 메꿔야하는 추가 작업 발생 → 성능 저하
-
정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼냄
-
성능이 키의 크기와 r의 선택에 영향을 받음
어떤 기수 r을 이용하여 정렬 키를 몇 개의 숫자로 분해
- r=10 : 키를 십진수로 분할
- r=2 : 키를 이진수로 분할
기수-r 정렬에서는 r개의 빈(bin)이 필요
- 정렬되어야 하는 레코드가 R1,,,Rn일 때, 레코드의 키는 기수-r을 이용하여 분할 -> 0~(r-1) 사이의 d자리 키가 된다
- 각 빈의 레코드는 빈의 첫 레코드를 가리키는 포인터와 마지막 레코드를 가리키는 포인터를 통해 체인으로 연결되며, 체인은 큐처럼 동작
기수 정렬은 정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않음
정렬 대상의 모든 길이가 동일해야 가장 효율적
※ 좋은 예) [123, 486, 309, 944], [blue, rice, pain, book] 등등
※ 나쁜 예) [5643, -43, 1, 87912], [sky, pencil, water, a] 등등
길이가 각각 다를경우 빈 공간을 메꿔야하는 추가 작업 발생 → 성능 저하
정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼냄
성능이 키의 크기와 r의 선택에 영향을 받음
-
정렬할 숫자들을 '버킷' 공간에 각 숫자와 동일한 위치에 저장
-
'버킷' 공간에 저장된 숫자들을 처음부터 다시 꺼내어 정렬 공간에 차례대로 저장
※ 버킷 공간의 크기는 숫자 길이와 동일
MSD(most-significant-digit-first) 정렬
- 최대 유효 숫자 우선 정렬
- '가장 큰 자릿수'부터 정렬을 진행
※ 가장 왼쪽부터
- '가장 큰 자릿수'부터 정렬을 진행
- 코드 구현은 LSD에 비해 추가 작업(정렬 상태 확인)이 필요하지만, 중간에 정렬이 완료될 수 있는 장점이 존재
숫자 '134, 224, 232, 122'를 오름차순으로 정렬
LSD(least-significant-digit-first) 정렬
- 최소 유효 숫자 우선 정렬
- '가장 작은 자릿수'부터 정렬을 진행
- 가장 오른쪽부터(숫자로 치면 1의 자리수부터)
- '가장 작은 자릿수'부터 정렬을 진행
- LSD가 MSD보다 더 단순
- 생성된 파일과 서브 파일을 독립적으로 정렬할 필요가 없으므로 오버헤드가 적게 든다
숫자 '134, 224, 232, 122'를 오름차순으로 정렬
구현
import java.util.Arrays;
public class Main{
static final int N = 10;
public static void main(String[] args) {
int[] arr = new int{134, 224, 232, 122};
System.out.println("정렬 전: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("정렬 후: " + Arrays.toString(arr));
}
public static void radixSort(int[] array) {
final int MAX_LENGTH = getMaxLength(array), myArrLen = array.length;
int myRadix = 1;
int[] sortedArray = new int[myArrLen], counts;
for (int p = 0; p < MAX_LENGTH; p++) {
counts = new int[10];
for (int numOfTemp : array) {
counts[(numOfTemp / myRadix) % 10]++;
}
for (int i = 1; i < 10; i++)
counts[i] += counts[i - 1];
for (int i = myArrLen - 1; i >= 0; i--) {
sortedArray[counts[(array[i] / myRadix) % 10]-- - 1] = array[i];
}
array = sortedArray;
sortedArray = new int[myArrLen];
myRadix *= 10;
}
System.out.println("정렬 후 : " + Arrays.toString(array));
}
public static int getMaxLength(int[] array) {
int max = 0;
for (int numOfTemp : array) {
if (max < numOfTemp)
max = numOfTemp;
}
return (int) Math.log10(max) + 1;
}
}
reference
- 고려대학교 김상곤 교수님 강의 중
- [ch 10-2] 복잡하지만 효율적인 정렬 알고리즘_3(기수 정렬)
- 기수 정렬(Radix Sort)
Author And Source
이 문제에 관하여([Sort] 기수 정렬(radix sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cham/Sort-기수-정렬radix-sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)