기수 정렬

기수 정렬은 다른 정렬과 다르게 서로 비교하여 정렬하지않습니다.
기수 정렬은 각 데이터의 자리수와 자리수의 값을 이용해 반복적으로 Counting Sort(계수 정렬)를 수행하여 전체 배열을 정렬하는 방식입니다.

계수 정렬이란?

원소간 비교하지않고 각 원소가 몇개 등장하는지 갯수를 세서 정렬하는 방법

• 시간 복잡도 : O(N)
  엄청나게 빠르지만, 요소 간 차이가 크거나 최대값 요소가 매우 클 경우 메모리 낭비가 심하다.

구현

const arr = [5, 4, 3, 2, 1, 1, 1, 1, 3, 4, 5, 5, 2, 2, 2]
const count = Array(5).fill(0) 
let sorted = []

for (let i = 0; i < arr.length; i++) {
	count[arr[i] -1]++;
}

for (let i = 0; i < count.length; i++) {
	const sortedNum = Array(count[i]).fill(i+1);
  sorted = sorted.concat(sortedNum);
}

function countingSort(arr) {
	const max = Math.max(...arr)
    const min = Math.min(...arr);
  let count = {}
  
  for (let i = min, i <= Max; i++) {
  	count[i] = 0; // min - max까지 0으로 채운 객체
  }
  for (let i = 0; i < arr.length; i++) {
  	count[arr[i]]++
  }

	let sortedArr = [];
for (let i = min; i < max; i++) {
  	while (count[i] > 0) {
  		sortedArr.push(i)
    	count[i]--;
	  }
	}
 return sortedArr; 
}

시간 복잡도

• 최악 시간 복잡도 : O(nk)
• 평균 시간 복잡도 : O(nk)
• 공간 복잡도 : O(n+k)

구현

const radixSort= (array) =>{
  let arr = [].concat(array);
  let max;
  let digitArr = new Array(10);
  for(let i = 0; i < digitArr.length ; i++){ //각 배열 안에 배열 생성
      digitArr[i] = [];
  }
  for(let i = 0 ; i < arr.length ; i++){ //최대 값 구하기
      if(i===0 || max < arr[i]){
          max = arr[i];
      }
  }
  let maxLog = Math.log10(max)+1;// 자리수 판별 //최대 자리수
  for (let digit = 1 ; digit <= maxLog ; digit++){ //1의 자리부터 최대자리수까지
      let digit10 = Math.pow(10,digit); 
      let tempArr = [];
      for(let i = 0 ; i < arr.length ;i++){
          if(digit === 1){ // 1의 자리일때
              digitArr[arr[i]%digit10].push(arr[i]);
          }else{
              tempDigit = Math.floor((arr[i]%digit10)*10/digit10);
              digitArr[tempDigit].push(arr[i]);
          }
      }

      for(let i = 0 ; i < digitArr.length ; i++){
          while(digitArr[i].length!==0){
              tempArr.push(digitArr[i][0]);
              digitArr[i].shift();
          }
      }
      arr = [].concat(tempArr);
  }

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

function digitCount(num) {
	return num.length; // 숫자의 자릿수
}

function mostDigits(nums) {
	let maxDigits = 0;
  	for (let i = 0; i < nums.length; i++) { //가장 긴 숫자의 길이를 구하는 것
    	maxDigits = Math.max(maxDigits, digitCount(nums[i]));
    }
  return maxDigits;
}

function radixSort(nums) {
	const maxDigits = mostDigits(nums) // 가장 긴 자릿수
    for (let k = 0; k < maxDigits; k++) {
    	let digitBuckets = Array.from({ length : 10}, () => []) // 각 자릿수마다, 빈배열 10개를 만듬!
        for (let i = 0; i < nums.length; i++) {
        	let digit = getDigit(nums[i], k); //배열의 하나하나, k는 자릿수
          digitBuckets[digit].push(nums[i]) //해당되는 순서에 집어넣기
        }
      nums = [].concat(...digitBuckets);
    }
  return nums;
}