[ Javascript ] 버블정렬

개념

버블 정렬은 처음부터 끝-1의 인덱스에 대해서 해당 인덱스의 오른쪽 값과 비교하여 값을 변경해주는, 간단한 정렬 알고리즘이다.

실제 값끼리 수를 비교하여 진행하므로 비교기반의 알고리즘이고, 추가적인 메모리가 필요하지 않다.

 

구현

const bubbleSort = (inputArray) => {
  for (let x = 0; x < inputArray.length; x++) {
    for ( let currentIndex = 0; currentIndex < inputArray.length - 1; currentIndex++ ) {
      if (inputArray[currentIndex] > inputArray[currentIndex + 1]) {
        let temp = inputArray[currentIndex + 1];
        inputArray[currentIndex + 1] = inputArray[currentIndex];
        inputArray[currentIndex] = temp;
      }
    }
  }
  return inputArray;
};

module.exports = bubbleSort;

전체 배열의 길이를 n이라 하면, 총 n번, n-1개의 원소들에 대해 비교를 수행한다.

따라서 시간복잡도를 표기하면 O(n^2)이다.

 

테스트코드

const 버블정렬 = require('../sort/bubbleSort');
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를 할 것이므로, testFunction을 회문하며 동일한 테스트케이스를 테스트했다.