[ Javascript ] 퀵 정렬

 

개념

파티션

퀵정렬은 임의의 값인 피봇을 지정(나같은 경우 배열의 첫값을 설정했다.)하고, 그 인덱스를 제외한 배열 들을 좌측과 우측끝에서 비교하며 진행한다.

 

좌측은 pivot보다 작은 경우 진행하고 우측은 pivot보다 큰 경우 진행한다.

좌측이 pivot보다 크면 좌측인덱스는 거기서 정지한다.

우측이 pivot보다 작으면 우측 인덱스는 거기서 정지한다.

더이상 진행이 되지않는데 좌측인덱스가 우측인덱스보다 왼쪽에 있으면 좌우측값을 교환한다.

 

이후, 좌측인덱스가 우측인덱스보다 커지면 pivot과 오른쪽인덱스를 교환하고, 오른쪽 인덱스를 반환한다.

이때 pivot은 배열에서 자기 위치에 맞는 위치를 갖게된다.

 

 

분할정복

파티션이 완료되면 해당 인덱스를 기준으로 왼쪽 배열과 오른쪽 정렬에 대해 파티션을 진행한다.

 

구현

const QuickSort = (inputArray, start, end) => {
  if (start >= end) return;
  const partition = getPartition(inputArray, start, end);
  QuickSort(inputArray, start, partition - 1);
  QuickSort(inputArray, partition + 1, end);
};

const getPartition = (inputArray, start, end) => {
  const pivot = inputArray[start];
  let left = start + 1;
  let right = end;

  while (left <= right) {
    while (left <= end && inputArray[left] <= pivot) left++;
    while (right > start && inputArray[right] > pivot) right--;

    if (left < right) {
      const temp = inputArray[left];
      inputArray[left] = inputArray[right];
      inputArray[right] = temp;
    }
  }

  inputArray[start] = inputArray[right];
  inputArray[right] = pivot;
  return right;
};

const QuickSortExecute = (inputArray) => {
  QuickSort(inputArray, 0, inputArray.length - 1);
  return inputArray;
};
module.exports = QuickSortExecute;

이러면 평균적으로 O(NlogN)의 시간복잡도를 갖지만, pivot이 어떻게 잡히냐에 따라 다른 시간복잡도를 갖는다.

즉, 불안정 정렬이다. 역순정렬인 경우 O(N^2)의 복잡도를 가진다.

 

파이썬과 같은 언어에서는 sort를 퀵소트의 pivot을 잘 조정하여 사용한다.

 

 

테스트코드

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