[알고리즘 | JS] sorting algorithm(정렬 알고리즘)6 - radix sort

이전에 배웠던 정렬알고리즘 5개는 기본적으로 comparison sorts(비교 정렬)이다.

배열의 요소를 하나 하나 비교하면서 정렬했던 것이기 때문이다.(e.g. 두 요소의 크기를 비교해서 어느 위치로 옮기고 하는 작업)

아래는 기존에 배웠던 정렬 알고리즘의 평균 시간 복잡도(big O표현)이다.

• bubble sort - O(n^2)
• Insetion sort - O(n^2)
• selection sort  - O(n^2)
• quick sort - O(n log (n))
• merge sort -  O(n log (n))

결과를 보면 알 수 있겠지만 최대 효율이나도 n log n이 한계이다. 

 

여기서 어떻게 더 발전할 수 있을까?

-> 비교를 통해 정렬하는 sort 알고리즘 외에 다른 유형의 sort 알고리즘이 존재한다.

이 다른 유형의 알고리즘은 데이터의 특별한 속성을 이용한다. 

 

 radix sort (기수 정렬)

- 비교를 통해 정렬하는 것이 아니라 데이터의 속성을 이용한 특별한 정렬 알고리즘

• 비교를 수행하지 않는다.(무엇이 더 작은 지, 큰 지 묻지 않음)
• 숫자로 작동한다(숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용).
  • e.g.) 자릿수가 더 큰 수, 예를 들어 4자리 수가 있다면 2자리 수보다 더 크다는 것
• 보통, 실제로 사용할 때는 이진수를 이용한다. + 원하는 문자열이나 이미지를 가져와 이진 형식으로 바꿀수도 있다(but, 정렬할 때 사용할 실제 데이터는 숫자여야만 한다!)
• digit은 0 과 9 사이의 수를 말한다. 
• 버킷 정렬의 일종으로 취급되기도 한다. 

1-1. 기수 정렬 helper 만들기

// TODO: 자릿수 알아내기 (getDigit)
{
  //abs는 음수를 고려하기 위해서 사용된 메서드
  function getDigit(num, i) {
    //Math.pow는 제곱 계산
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
  }
  console.log(getDigit(2234, 3));
  //100의 자리에 있는 수를 구하는 거니까 3을 i로 잡고 2234에서 2를 리턴

  function digitCount(num) {
    //digitCount ->num이 몇자리 수인지 알려주는 함수
    //Math.log10 -> 밑이 10인 로그, 10의 어떤 거듭제곱으로 이 수(num)가 되는 지 묻는다.
    //num이 0일 경우에는 log10을 할때 infinity값을 갖게되기때문에 return 1 을 해준다.
    if (num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num))) + 1;
  }
  console.log(digitCount(2235234)); // 7 (7자리수)

  //TODO: mostDigits(nums) -> 인자로 숫자들이 담긴 배열을 주고 가장 큰 숫자의 digits를 반환한다.
  function mostDigits(nums) {
    let maxDigits = 0;
    // Math.max(0,12) => 두 숫자 중 더 큰 수를 반환한다.

    //if문을 사용해서 x(최대 자릿수)가 현재 최댓값보다 클 경우 현재 최댓값으로 재할당하도록 작성하는 대신
    //자릿수 최댓값(maxDigits)를 현재 최댓값과 nums[i]의 자릿수 계산(digitCount)중 큰 값과 같도록 설정할 수 있다.
    for (let i = 0; i < nums.length; i++) {
      maxDigits = Math.max(maxDigits, digitCount(nums[i]));
    }
    return maxDigits;
  }
}

• 숫자 값이 아니라 해당 자리의 값(digit)을 구하는 것이므로 왼쪽부터 오른쪽으로가 아니라 오른쪽부터 왼쪽으로 찾는다. (10의 0제곱 = 1  오른쪽부터 0번째 자리, 10의 1제곱 =  오른쪽부터 1번째 자리, 10의 2제곱, 오른쪽부터 2번째자리)

// getDigit(num, place) - returns the digit in num at the given place value
getDigit(12345, 0); // 5
getDigit(12345, 1); // 4
getDigit(12345, 2); // 3
// digit 은 왼쪽부터가 아니라 오른쪽부터 카운트이다. 0번째 요소니까 5를 리턴한다.

1-2. 기수 정렬 구현

// TODO: Radix sort function
// loop는 maxDigits 만큼 돈다.
// 각 loop의 순회에 bucket을 만든다. *bucket은 []빈배열이다.
{
  //위에 만든 helper 함수 --- 생략 ----

  function radixSort(nums) {
    let maxDigitsCount = mostDigits(nums);
    for (let k = 0; k < maxDigitsCount; k++) {
      //Array.from으로 배열 10개를 만들어준다.
      let digitBuckets = Array.from({ length: 10 }, () => []);
      for (let i = 0; i < nums.length; i++) {
        let digit = getDigit(nums[i], k); //digit이 3이면 3번 버켓에 넣어줘야한다.
        digitBuckets[digit].push(nums[i]);
      }
      console.log('digitBuckts :', digitBuckets);
      nums = [].concat(...digitBuckets);
      console.log('nums :', nums);
    }
    return nums;
  }
  radixSort([223, 1, 2464, 7456, 234, 4, 2, 664]);
}

2. 기수 정렬의 시간 복잡도

최상, 평균, 최악의 시간 복잡도: O(nk)이다. 

• n은 정렬할 항목 수나 정수의 수이고, k는 기수의 도메인 크기
• n: length of array (배열의 길이로, 정렬하려는 수의 갯수)
• k: number of digits(average)
• 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 
• 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없다. 
• 주의) 모든 수가 고유하고, 무작위로 분산된 데이터를 다룰 때에는 n log n이 된다. 
• 하지만 위의 경우가 아니라면 보통의 비교 정렬 알고리즘보다 빠르다.

* 공간 복잡도: O(n + k) // k는 기수의 도메인 크기 

• 여기서 도메인이란 하나의 속성에서 취할 수 있는 값의 범위를 말한다.

여담:

기수정렬의 k은 가장 큰 요소의 자릿수가 아니라 큰 값 그 자체를 말한다고 한다. 

chatGPT answer:

아니요, 기수 정렬에서 k는 정렬되는 요소의 최대값을 나타내며 최대값의 자릿수가 아닙니다.

예를 들어 다음과 같은 숫자 목록이 있다고 가정해 보겠습니다: {170, 45, 75, 90, 802, 24, 2, 66}과 같은 숫자 목록이 있다면 이 목록의 최대값은 802이므로 k는 802와 같습니다. 802의 자릿수가 세 자리라는 사실은 k의 값과 직접적인 관련이 없습니다.

k의 값은 정렬에 필요한 버킷의 수를 결정하는 데 사용됩니다. 구체적으로 말하자면, 각 버킷은 다양한 값을 담을 수 있는 k개의 버킷이 필요합니다. 예를 들어, k가 802이면 가장 큰 숫자에 대해 802개의 버킷이 필요합니다. 그러나 실제로는 일반적으로 버킷당 값 범위로 값을 그룹화한 다음 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하여 범위 내에서 각 버킷을 정렬함으로써 더 적은 수의 버킷을 사용합니다.

기수 정렬의 시간 및 공간 복잡성은 k의 값과 정렬되는 요소의 자릿수, 정렬되는 요소의 수에 따라 달라집니다.

 

기수 정렬 animation 링크