[알고리즘] 퀵정렬 (자바스크립트)

퀵 정렬 (Quick Sort)

기본적으로 배열 요소 갯수가 0이나 1개가 될 때까지 쪼개는 합병정렬과 유사하다. 여기서 피벗포인트라 부르는 단일 요소를 선택하여 수행하는 것이 차이점이다. 중앙점이 아닌, 이 피벗포인트를 기준으로 배열을 한 번 순회하여 기준보다 작은 수를 왼쪽 그룹으로, 큰 수를 오른쪽 그룹으로 이동시킨다.

 

로직을 이해하고 구현하는 데에 난이도가 좀 있는.. 알고리즘이다.

 

1. 피벗 헬퍼

앞선 합병정렬에서 합병로직을 먼저 구현했던 것처럼, 퀵정렬에서도 피벗 헬퍼를 통해 퀵정렬에 사용할 메서드를 모듈화해준다. 피벗 헬퍼는 주어진 배열 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치한다. 좌/우 배열 내의 정렬 여부는 당장 중요하지 않다.

 

피벗의 선택 기준

배열의 모든 요소 값들을 알고 있는 상태에서 그 중간값을 선택하면 좌/우 배열이 균형있게 나뉘어 지겠지만, 그렇지 않기 때문에 보통 항상 첫 번째 요소, 혹은 마지막이나 무작위 요소 인덱스로 설정할 수 있다. 본 구현에서는 각 배열의 첫 번째 요소를 피벗으로 설정하여 진행된다.

 

의사코드

1. 첫 번째 원소를 기준으로, 모든 배열 값을 비교한다. 기준 인덱스가 i=0이라면, 기준보다 작은 값을 i+1, i+2.. 번째로 쌓아나간다. 더 이상 기준보다 작은 원소가 없다면 마지막으로 쌓인 원소와 기준 원소의 위치를 바꿔준다.
2. (1)의 결과로 기준점보다 작은 수의 그룹은 좌측 배열에, 큰 수의 그룹은 우측 배열에 남게 되었다. 

구현

function pivotHelper(arr) {
  let pivotPoint = 0;
  let cnt = 1;

  for (let i = 1; i <= arr.length - 1; i++) {
    if (arr[pivotPoint] > arr[i]) {
      let tmp = arr[i];
      arr[i] = arr[cnt];
      arr[cnt] = tmp;
      cnt++;
    }
    console.log(arr);
  }

  let cntTmp = arr[cnt - 1];
  arr[cnt - 1] = arr[pivotPoint];
  arr[pivotPoint] = cntTmp;

  return arr;
}

let arr = [32, 23, 17, 26, 27, 47, 39, 12, 43];

pivotHelper(arr);

그러나 재귀적으로 활용하기 위해선 위와 같이 코드를 구현하면 안된다. 인덱스를 반환하고, 시작, 끝 값을 입력으로 받아야 한다.

 

function pivot(arr, start = 0, end = arr.length + 1) {
  function swap(array, i, j) {
    var tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }

  var pivot = arr[start];
  var swapIdx = start;

  for (var i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  swap(arr, start, swapIdx);
  return swapIdx;
}

 

2. 구현

의사코드

1. 입력받은 배열에서 첫 번째 요소를 시작 피벗 포인트로 지정, 피벗 헬퍼 메서드를 실행하여 이동한 인덱스를 반환한다.
2. 반환한 인덱스를 기준으로 나뉘어진 양 쪽 배열을 재귀적으로 반복한다.
3. 주의할 점은 새로운 배열을 만드는 것이 아닌, 기존 배열에서 피벗 인덱스를 고정시키고 변경해가며 정렬이 이루어진다는 것이다.
4. 중단점을 설정하는 게 좀 어려운데, End 인덱스 파라미터가 Start 인덱스 파라미터를 역전했을 때 루프를 재귀를 탈출한다. 

구현

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    // left
    quidkSort(arr, left, pivotIdx - 1);
    // right
    quidkSort(arr, pivotIdx + 1, right);
  }
  console.log(arr);
  return arr;
}

 

퀵정렬의 계산 복잡도

기본적으로 합병정렬과 동일한 O(n log n)의 복잡도를 갖는다. 그러나 피벗 포인트로 설정한 값이 가장 작은 값이거나 가장 큰 값이라 배열 그룹이 한 쪽으로 몰리게 된다면, O(n) x O(n) 연산이 이루어져 O(n^2)의 복잡도를 갖게 된다.