[ Javascript ] 계수정렬

개념

계수정렬은 굉장히 특이한 녀석이다. 똑같은 수가 많이 존재하는 배열을 정렬하는데 가장 좋다.

로직은 무식하게 각 숫자의 갯수를 세는 것

괜히 영어로 CountingSort가 아니다.

구현

const countingSort = (inputArray) => {
  const maxNumber = Math.max(...inputArray);
  const result = [];
  const countArray = Array.from({ length: maxNumber + 1 }).map(() => 0);
  inputArray.forEach((num) => {
    countArray[num]++;
  });
  countArray.forEach((numberCount, index) => {
    for (let x = 0; x < numberCount; x++) {
      result.push(index);
    }
  });
  return result;
};

module.exports = countingSort;

매우간단하다.

배열을 딱 한번만 회문하면 되니 매우 빠르지만, 공간을 많이 잡아먹는다는 단점이 있다.

 

테스트코드

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 계수정렬 = require('../sort/countingSort');
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);
    });
  });
});
test(`계수정렬 테스트`, () => {
  expect(계수정렬([3, 3, 1, 1, 2, 2, 2, 7, 7, 7, 4, 4])).toEqual([
    1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 7, 7,
  ]);
});

이걸로 정렬시리즈는 끝났다.