[ Javascript ] 삽입정렬

개념

전체 배열을 돌면서 현재 인덱스를 진행시키는데, 이때 값은 key라고 한다면,

key가 현재인덱스값보다 작을때까지,

현재 인덱스를 배열의 왼쪽끝까지 옮겨가며 값을 비교한 뒤에, 현재인덱스값을 현재인덱스-1의 값으로 바꾸고 인덱스를 줄인다.

이 과정이 끝나면, key를 현재 인덱스에 넣어준다.

구현

const insertSort = (inputArray) => {
  for (let index = 1; index < inputArray.length; index++) {
    let key = inputArray[index];
    let currentIndex = index;
    while (currentIndex > 0 && inputArray[currentIndex - 1] > key) {
      inputArray[currentIndex] = inputArray[currentIndex - 1];
      currentIndex--;
    }
    inputArray[currentIndex] = key;
  }
  return inputArray;
};

module.exports = insertSort;

얘도 선택정렬, 버블정렬과 마찬가지로 O(n^2)이다.

 

테스트 코드

const 버블정렬 = require('../sort/bubbleSort');
const 선택정렬 = require('../sort/selectionSort');
const 삽입정렬 = require('../sort/inesertSort');
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);
    });
  });
});