데이터 구조 및 알고리즘 - 기수 정렬

내가 "배운"이전 두 중간 정렬 알고리즘은 비교 정렬이었습니다. 가장 기본적인 수준에서 값을 비교하고 교환했습니다. 그리고 지금 생각해보면 초등부도 마찬가지입니다. 한 가지 기억해야 할 것은 이러한 비교 정렬로 달성할 수 있는 최고의 시간 복잡도는 대수적이라는 점입니다. 이것은 끔찍하지는 않지만 더 나은 작업을 수행하고 싶습니다. 여기에서 Radix 정렬이 필요합니다. 주목해야 할 한 가지는 기수입니다. 정렬 및 기타 비비교 정렬은 다른 정렬 알고리즘보다 더 나은 시간 복잡도를 보장하지 않으며 특정 경우에만 훨씬 더 효율적입니다. 기수 정렬은 일반적으로 이진수인 숫자 목록에서 작동하는 특수 정렬 알고리즘입니다. 실제로 문자열 목록을 정수로 변환한 다음 기수 정렬을 사용할 수 있지만 그 시점에서 다른 유형을 선택하는 것이 좋습니다. 이 알고리즘이 작동하는 방식은 숫자의 크기에 대한 정보가 자릿수로 인코딩된다는 사실을 이용하는 것입니다. 그래도 정확히 무엇을 의미합니까?

숫자의 자릿수가 더 많으면 더 큰 숫자입니다. 300은 3자리(3,0,0)이고 95는 2자리(9,5)이므로 300이 95보다 크다는 것을 숫자를 기준으로 안전하게 가정할 수 있습니다. 이것이 작동하는 방식(지금은 소수가 아닌 기본 10 숫자용임)은 0-9까지 10개의 "버킷"이 있고 마지막(가장 오른쪽) 숫자를 기준으로 각 버킷에 숫자를 배치하는 것입니다. 버킷 내에서 정렬하지 않고 그냥 버킷에 배치합니다. 그런 다음 버킷 순서에 따라 목록에 다시 배치하므로 9가 1000보다 작더라도 가장 오른쪽 숫자가 0인 경우 1000이 첫 번째가 됩니다. 이제 오른쪽에서 두 번째 숫자를 기준으로 프로세스가 반복됩니다. . 오른쪽에서 두 번째 숫자가 없는 숫자, 예를 들어 9는 오른쪽에서 두 번째 숫자가 0이므로 0 버킷에 배치됩니다. 가장 큰 값에 도달할 때까지 이 프로세스를 계속 반복합니다. 이 과정을 반복하는 횟수는 가장 큰 자릿수 숫자만큼입니다.
. 다음은 진행 상황을 보여주는 예입니다.

기수 정렬을 구현하려면 이전과 마찬가지로 pivot , swap , merge 등 몇 가지 도우미 함수를 작성해야 합니다. 작성해야 하는 도우미 함수 중 하나는 메서드입니다. 주어진 장소에서 숫자의 숫자를 반환합니다. 따라서 getDigit(number, place) 다음 결과를 예상할 수 있습니다.

getDigit(93824, 0);  //4
getDigit(93824, 1);  //2
getDigit(93824, 2);  //8
getDigit(93824, 3);  //3
getDigit(93824, 4);  //9

이것에 대한 힌트 힌트 바퀴를 재발 명할 이유가 없습니다. Stackoverflow에는 많은 솔루션이 있으며 다음은 그 중 하나입니다.

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

우리가 만들어야 할 다음 도우미 메서드는 숫자에 몇 개의 자릿수가 있는지입니다. 왜요? 가장 큰 것은 버킷으로 정렬/재주문할 횟수를 결정하는 방법이기 때문입니다. 이것을 digitCount(number)라고 부르면 Stackoverflow에서 더 훌륭한 코드를 얻을 수 있습니다.

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

생성할 마지막 메서드는 주어진 숫자 배열이 해당 배열에서 가장 큰 값digitCount을 반환하는 메서드이며 보시다시피 이전에 정의한 메서드를 사용할 것입니다. Math.max(num1, num2)를 사용하여 최대값을 비교하고 반환할 수 있습니다. 시작합니다:

function mostDigits(numbers) {
    let maxDigits = 0;
    for(let i = 0; i < numbers.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(numbers[i]));
    }
    return maxDigits;
}

실제 기수 정렬의 경우 다음이 필요합니다.

가장 큰 자릿수 찾기 ( mostDigits() )

0에서 이전 단계로 돌아갈 때까지 루프를 시작합니다

.

각 자릿수에 대한 버킷을 생성합니다. 이 버킷은 각각 빈 상태로 시작하는 10개의 하위 배열이 있는 배열입니다.

비교할 "숫자"를 기준으로 적절한 해당 버킷에 각 숫자를 배치합니다(여기서는 'getDigit()` 사용).

배열(재주문)을 버킷의 값(0 -> 9)으로 바꿉니다

.

목록 반환(모든 정렬된 woot woot!!!!)
Radix Sort .