[ Javascript ] 큐과 기수정렬

큐

큐는 간단하다. FIFO. First In First Out

먼저들어온게 먼저나가는 자료구조이다.

 

원래는 링크드리스트로 구현하지만, 배열로 간단하게 구성해주었다.

class Queue {
  constructor() {
    this.queue = [];
  }
  inqueue(value) {
    this.queue.push(value);
  }
  dequeue() {
    const [node, ...newQueue] = this.queue;
    this.queue = newQueue;
    return node;
  }
  isEmpty() {
    return this.queue.length === 0;
  }
}
module.exports = Queue;

기수정렬

개념

양수를 정렬하는경우, 0부터 9까지의 각각 큐를 준비한다.

제일 큰 숫자의 자리수만큼 반복하며, 처음에는 1의 자리 수에 맞는 큐에 집어넣는다.

1의자리수의 순회가 끝나면 0부터 9까지 큐가 빌때까디 dequeue시키며 중간 결과 result를 만든다.

 

그러면 중간결과 result를 다시 순회하며, 이번에는 10의자리 수에 해당하는 큐에 집어넣는다.

....

이를 가장 큰 숫자의 자리수만큼 반복한다.

 

구현

const Queue = require('../dataStructure/queue/Queue');
const radixSort = (inputValue) => {
  const maxValue = Math.max(...inputValue); 
  const digit = String(maxValue).split('').length;//최대 자리수
  const zeroToNine = Array.from({ length: 10 }).map(() => new Queue()); //0~9까지의 각 큐
  
  let result = [...inputValue];
  for (let x = 1; x < digit + 1; x++) {
    result.forEach((number) => {
      const string = String(number).split('');
      let index = string.length >= x ? string[string.length - x] : 0; //해당 자리수가 없는 경우
      zeroToNine[index].inqueue(number); //큐에 집어넣기
    });

    result = [];
    zeroToNine.forEach((q) => {
      while (!q.isEmpty()) {
        result.push(q.dequeue()); //큐에 있는거 다 꺼내기
      }
    });
  }
  return result;
};

module.exports = radixSort;

이러면 4자리면 배열을 4번만 회문하면 결과가 나오게 된다.

O(dN)인 것. 속도도 안정적이고 빠르다는 특성을 갖는다.

배열 알고리즘 중에 로직이 간단하면서도 안정적이고 좋은 성능을 보여줘서 나는 되게 좋아한다.

 

 

테스트코드

const 버블정렬 = require('../sort/bubbleSort');
const 힙정렬 = require('../sort/heapSort');
const 삽입정렬 = require('../sort/insertSort');
const 합병정렬 = require('../sort/mergeSort');
const 퀵정렬 = require('../sort/quickSort');
const 선택정렬 = require('../sort/selectionSort');
const 기수정렬 = require('../sort/radixSort');
const testData = [
  {
    testInput: [5, 3, 1],

    testAnswer: [1, 3, 5],
  },
  {
    testInput: [5, 3, 1, 5, 3, 22],
    testAnswer: [1, 3, 3, 5, 5, 22],
  },
  {
    testInput: [5, 3, 100, 1, 5, 99, 3, 22],
    testAnswer: [1, 3, 3, 5, 5, 22, 99, 100],
  },
  {
    testInput: [8, 9, 8, 8, 9, 8, 9],
    testAnswer: [8, 8, 8, 8, 9, 9, 9],
  },
  {
    testInput: [1, 9, 7, 8, 6, 8, 9],
    testAnswer: [1, 6, 7, 8, 8, 9, 9],
  },
];

const testFunction = [
  선택정렬,
  삽입정렬,
  버블정렬,
  합병정렬,
  퀵정렬,
  힙정렬,
  기수정렬,
];
testFunction.forEach((func) => {
  testData.forEach((testData, index) => {
    test(`${func.name} 테스트 ${index}`, () => {
      expect(func(testData.testInput)).toEqual(testData.testAnswer);
    });
  });
});