알고리즘, Sort, Radix Sort

Radix Sort(기수 정렬)은 정수나 문자열의 자릿수를 기준으로 정렬하는 효율적인 정수 정렬 알고리즘입니다. 이 알고리즘은 주로 양의 정수나 고정 길이의 문자열을 정렬하는 데 사용되며, 시간 복잡도가 O(d * (n + k))로, 비교 기반 정렬 알고리즘보다 더 효율적일 수 있습니다. 여기서 d는 데이터의 최대 자릿수, n은 요소의 수, k는 기수(예: 10진법에서는 10)입니다.

기본 개념

기수 정렬은 LSD(Least Significant Digit)와 MSD(Most Significant Digit) 두 가지 방법으로 나뉩니다:

• LSD 방식: 가장 작은 자릿수부터 시작하여 큰 자릿수 방향으로 정렬합니다.
• MSD 방식: 가장 큰 자릿수부터 시작하여 작은 자릿수 방향으로 정렬합니다.

LSD 방식은 일반적으로 더 많이 사용됩니다.

과정

1. 최대 자릿수 결정: 데이터 중 가장 큰 수의 자릿수를 구합니다.
2. 자릿수별 정렬: 각 자릿수에 대해 정렬을 수행합니다. 이때, 안정 정렬 알고리즘(예: Counting Sort)을 사용하여 정렬합니다.

예제

다음은 자바스크립트로 구현한 기수 정렬의 예제입니다(LSD 방식).

function getDigit(num, place) {
    return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

function digitCount(num) {
    if (num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(nums) {
    let maxDigits = 0;
    for (let num of nums) {
        maxDigits = Math.max(maxDigits, digitCount(num));
    }
    return maxDigits;
}

function radixSort(nums) {
    let maxDigitCount = mostDigits(nums);
    for (let k = 0; k < maxDigitCount; k++) {
        let digitBuckets = Array.from({ length: 10 }, () => []);
        for (let i = 0; i < nums.length; i++) {
            let digit = getDigit(nums[i], k);
            digitBuckets[digit].push(nums[i]);
        }
        nums = [].concat(...digitBuckets);
    }
    return nums;
}

let arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(arr)); // [2, 24, 45, 66, 75, 90, 170, 802]

 

시간 복잡도

기수 정렬의 시간 복잡도는 다음과 같습니다:

• 최악의 경우 시간 복잡도: O(d * (n + k))
• 평균 시간 복잡도: O(d * (n + k))
• 최선의 경우 시간 복잡도: O(d * (n + k))

여기서 d는 데이터의 최대 자릿수, n은 요소의 수, k는 기수(예: 10진법에서는 10)입니다.

특징

1. 비교 기반 정렬이 아님: 요소들을 비교하지 않고 자릿수를 기준으로 정렬합니다.
2. 안정 정렬: 동일한 값의 요소들이 입력 순서를 유지합니다.
3. 제자리 정렬이 아님: 추가적인 메모리 공간이 필요합니다.

장점

1. 효율성: 특정 조건에서 비교 기반 정렬보다 효율적일 수 있습니다.
2. 안정성: 동일한 값의 요소들이 입력 순서를 유지합니다.

단점

1. 제자리 정렬 아님: 추가적인 메모리 공간이 필요합니다.
2. 데이터 타입 제한: 주로 정수나 고정 길이 문자열에만 적용할 수 있습니다.
3. 자릿수에 민감: 데이터의 자릿수가 많을 경우 성능이 떨어질 수 있습니다.

결론

기수 정렬은 정수나 고정 길이 문자열을 정렬하는 데 매우 효율적인 알고리즘입니다. 비교 기반 정렬 알고리즘에 비해 더 나은 성능을 보일 수 있지만, 데이터 타입과 자릿수에 제한이 있습니다. 큰 데이터셋이나 자릿수가 많은 데이터의 경우, 기수 정렬의 성능이 떨어질 수 있습니다. 이러한 경우 다른 정렬 알고리즘과 병행하여 사용하거나, 상황에 맞는 알고리즘을 선택하는 것이 좋습니다.