[ Javascript ] 병합정렬

개념

병합정렬은 배열의 중간 인덱스를 찾고, 그 값을 기준으로 반을 나눈다.

이걸 배열 길이가 1일때까지 반복한 뒤에, merge라는 함수를 통해 나눴던 두 배열을 동시에 인덱스를 진행시키며 새로운 배열에 결과를 저장한다. 이걸 다시 원본 배열에다가 복사해 넣어주면된다.

이게 재귀적, 병렬적으로 일어나기 때문에 아주 빠르고 안정적으로 작동한다.

구현

mergeSort

이 함수가 배열의 중간 인덱스를 찾아서 반으로 나눈 뒤 배열의 길이가 1일때까지 재귀적으로mergeSort를 부른다.

이후, 나눈 인덱스 기준 왼쪽배열과 오른쪽배열의 처리가 끝났다면, 두 배열을 다시 merge해준다.

const mergeSort = (inputArray, left, right) => {
  if (left < right) {
    let mid = parseInt((left + right) / 2);
    mergeSort(inputArray, left, mid);
    mergeSort(inputArray, mid + 1, right);
    merge(inputArray, left, mid, right);
  }
};

merge

sortedArray라는 right-left+1의 크기를 가진 새로운 배열을 만들고,

left배열과 right배열의 값을 동시에 비교하여 sortedArray에 진행인덱스 값에 left가 크면 left를 넣고, right가 크면 right를 집어넣는다.

const merge = (inputArray, left, mid, right) => {
  let i = left;
  let j = mid + 1;
  let k = left;
  const sortedArray = Array.from({ length: right - left + 1 });
  while (i <= mid && j <= right) {
    if (inputArray[i] <= inputArray[j]) {
      sortedArray[k++] = inputArray[i++];
    } else {
      sortedArray[k++] = inputArray[j++];
    }
  }
  while (i <= mid) {
    sortedArray[k++] = inputArray[i++];
  }
  while (j <= right) {
    sortedArray[k++] = inputArray[j++];
  }
  for (let l = left; l <= right; l++) {
    inputArray[l] = sortedArray[l];
  }
};

mergeExecute

const mergeExecute = (inputArray) => {
  mergeSort(inputArray, 0, inputArray.length - 1);
  return inputArray;
};

module.exports = mergeExecute;

이렇게 병렬적으로 작동하게 된다.

 

전체코드

const mergeSort = (inputArray, left, right) => {
  if (left < right) {
    let mid = parseInt((left + right) / 2);
    mergeSort(inputArray, left, mid);
    mergeSort(inputArray, mid + 1, right);
    merge(inputArray, left, mid, right);
  }
};
const merge = (inputArray, left, mid, right) => {
  let i = left;
  let j = mid + 1;
  let k = left;
  const sortedArray = Array.from({ length: right - left + 1 });
  while (i <= mid && j <= right) {
    if (inputArray[i] <= inputArray[j]) {
      sortedArray[k++] = inputArray[i++];
    } else {
      sortedArray[k++] = inputArray[j++];
    }
  }
  while (i <= mid) {
    sortedArray[k++] = inputArray[i++];
  }
  while (j <= right) {
    sortedArray[k++] = inputArray[j++];
  }
  for (let l = left; l <= right; l++) {
    inputArray[l] = sortedArray[l];
  }
};

const mergeExecute = (inputArray) => {
  mergeSort(inputArray, 0, inputArray.length - 1);
  return inputArray;
};

module.exports = mergeExecute;

O(NlogN)의 시간복잡도를 갖게되며, 배열의 반을 기준으로 나눠서 진행하기때문에 안정적인 속도를 갖게된다.

다만, merge단계에서 새로운 배열을 만들기때문에 임의의 새로운 메모리를 정렬시 필요로 하게된다는 단점이 있다.

 

테스트코드

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