Radix Sort (기수 정렬) 알고리즘

Radix Sort

다른 정렬 알고리즘들과 달리 비교 작업을 수행하지 않는 정렬 알고리즘이며 숫자형 데이터만을 정렬할때 사용한다.

문자열이나 이미지 데이터를 가저와 이진형태로 변환후 정렬이 가능하지만 정렬할때의 실제 데이터는 숫자여야만한다.

 

정렬하려는 배열을 받은후 10개(10진수)의 버킷을 만든다.

받은 숫자형 데이터들의 첫번째 자릿수를 해당되는 버킷에 배치시킨후 버킷의 순서대로 배열을 재배치 시킨다.

이후 재배치된 데이터들의 두번째 자릿수를 이용하여 동일한 작업을 진행하며 반복적으로 작업을 수행하며 필요에 따라 반복적으로 계속해서 진행된다.

몇개의 보조 함수들이 필요하며 배열의 가장 큰수를 구하고 그수가 가진 자릿수를 구하며 데이터의 특정 자릿수에대한 값을 구하는 함수들이 필요하다.

 

 

최대 자릿수 알아내기 함수

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

function digitCount(num) {
  let string = num.toString();
  return string.length;
}

받은 숫자를 절대값으로 만들어준뒤 Math.log10() 함수를 이용하여 10제곱의 지수를 구해준뒤 소수를 버리고 +1해주면 그수의 최대 자릿수를 알아낼수 있다. 숫자 0을 log10 해주면 -Infinity값을 리턴하므로 이경우 1을 반환해준다.

 

어렵다면 간단하게 받은 숫자형 데이터를 문자열로 바꿔주고 길이를 구한후 반환해주면된다.

 

 

배열의 가장 큰수 구하기 함수

function mostDigits(arr) {
  let maximum = 0;
  for (let value of arr) maximum = Math.max(digitCount(value), maximum);
  return maximum;
}

먼저 정렬할 배열을 받은후 배열의 가장큰수를 저장할 변수를 생성한다. 이후 반복문을 생성한후 위에 작성한 digitCount()함수를 이용해 배열의 가장 큰 자릿수를 구해서 반환해준다. 이후 나중에 Radix Sort 함수내에서 구한 자릿수 만큼 반복하여 정렬작업을 수행한다.

 

 

원하는 자릿수의 값 구하기 함수

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

function getDigit(num, i) {
  let numToString = num.toString();
  let result = Number(numToString[numToString.length - i - 1]);
  if (isNaN(result)) return 0;
  return result;
}

받은 숫자형 데이터를 절대값으로 변환시킨후 10의 자릿수만큼의 제곱값을 나눠준다. 이후 소수를 버리고 10으로 나눈 나머지값을 반환해준다.

 

어렵다면 두번째 함수와 같이 받은 데이터를 문자열로 바꿔 다시 숫자형 데이터로 바꾼뒤 반환해 줄수도 있다.

 

 

Radix Sort 함수

function radixSort(arr) {
  const count = mostDigits(arr);
  for (let i = 0; i < count; i++) {
    let bucket = Array.from({ length: 10 }, () => []);
    for (let value of arr) {
      bucket[getDigit(value, i)].push(value);
    }
    arr = [].concat(...bucket);
  }
  return arr;
}

 

 

1. 정렬되지 않은 배열을 받은후 위에 작성한 mostDigits()함수를 이용하여 배열안 데이터들의 최대 자릿수를 구하고 구한 값만큼 반복문을 돌린다. 
2. 반복문 안에서 0부터 9까지의 값을 가진 데이터를 넣어줄 버킷으로 사용할 총 10개의 배열을가진 배열을 생성해주고 처음 받은 배열의 데이터 수만큼 내부 반복문을 생성해준다.
3. 이후 getDigit()함수를 이용해서 처음 받은 배열의 모든 데이터의 첫번째 자릿수의 값을 구한뒤 그 값에 맞는 버킷에 데이터를 넣어주고 내부 반복문이 끝나면 concat() 함수를 이용하여 버킷의 배열들을 하나의 배열로 합처준다.
4. 모든 작업이 끝나면 외부 반복문을 통해 두번째, 세번째, 필요한 자릿수까지 반복하여 작업하며 마지막에 재배치된 배열을 반환해준다.

 

 

Big O notation

최상, 최악, 평균 시간 복잡도는 O(nk), 즉 배열의 길이와 최대자릿수에 대한 반복수의 곱이 된다. 

사실 기수정렬의 시간복잡도에 대해서는 많은 의견들이 있는데 너무 어려워서 이해하기를 포기했다...