quickSort / 퀵정렬

1. 소개

quicksort는 1960년에 찰스 앤서니 리처드 호어라는 사람이 처음 제안했고, 수정과 보완을 거쳐 완성된 알고리즘이라고 한다. 이름 그대로 아직까지도 가장 빠른 알고리즘 중 하나라고 한다. 문제를 잘게 쪼개고, 쪼개진 문제들을 재귀적으로 해결하는 Divide and Conquer 전략을 이용한다.

 

2가지 풀이법이 있는데, Not in place, in place 방법이 있다. 인자로 받아오는 정렬되지 않은 배열 외에 외부의 배열을 만드는 방법이 not in place, 인자로 받아오는 배열 내부에서 바로 정렬하는 방법이 in place 방법이다. 예상할 수 있듯이 not in place 방법은 추가적인 메모리가 요구되므로 in place 방법이 선호된다.

 

시간복잡도는 평균적으로는 O(NlogN), 최악의 경우는 O(N^2)이 된다. 상세한 내용은 아래에 기술하였다.(참조2 유튜브 영상 내용)

 

---

2. 풀이

기준이 되는 원소를 pivot으로 지정하고, 그 원소를 기준으로 좌우로 나누어 가는 개념으로 생각하면 된다.

 

2-1. Not in place

이 방법은 배열 내부의 중복되는 데이터는 순서대로 pivot 배열에 삽입되므로 정렬 전 중복 데이터의 순서가 바뀌지 않는 stable한 정렬을 구현할 수 있다.

 

해결과정

배열을 인자로 받아와서, 길이가 1이면 바로 반환한다. (Base case)

배열의 길이가 1보다 크면, pivot을 지정한다. 아래 코드에서는 배열의 맨 앞쪽 요소를 지정하였으나, 어떤 위치든 상관이 없다. 그리고 나서 이 pivot 값을 기준으로 각 요소가 pivot값 이하이면 left 배열에 삽입, 초과이면 right 배열에 삽입한다.

left와 right로 쪼개진 각 배열에 대해서 재귀적으로 quickSort함수를 호출하여 배열의 길이가 1이 될때까지 반복한다. 각 결과를 leftSorted, rightSorted로 저장한다.

마지막으로 17번 줄과 같이 정렬된 배열을 반환한다.

function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
     left.push(arr[i]);
    } else {
     right.push(arr[i]);
    } 
  }
  const leftSorted = quickSort(left);
  const rightSorted = quickSort(right);
  return [...leftSorted, pivot, ...rightSorted];
}

2-2. In place

2-1. Not in place 방법과 다르게 메모리 공간이 절약되지만, unstable한 정렬 방법이다.

 

//default function parameter로 left, right를 지정한다.
const quickSort = function (arr, left = 0, right = arr.length - 1) {
  //배열의 중간값을 pivot으로 잡는다.
  //divide 함수 실행 결과로 반환되는 새로운 left 값을 newLeft로 지정한다.
  let mid = parseInt((left + right) / 2);
  let pivot = arr[mid];
  let newLeft = divide(arr, left, right, pivot);
  //Base case  
  if (left >= right) {
    return;
  }
  //divide function
  function divide(arr, left, right, pivot) {
    while (left <= right) {
      while (arr[left] < pivot) {
        left++;
      }
      while (pivot < arr[right]) {
        right--;
      }
      if (left <= right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
      }
    }
    return left;
  }
  //execution
  quickSort(arr, newLeft, right);
  quickSort(arr, left, newLeft - 1);
  return arr;
};

 

바로 이해가 어려우므로 도식을 보면서 이해해보자.

 

0) 배열의 중앙을 pivot으로 둔다. pivot= 10, 볼드체

1) left 위치의 3과 right 위치의 32는 pivot = 10 보다 각각 작고, 크므로 index만 1개씩 증가, 감소 시킨다.

2) 15, 9는 pivot = 10보다 각각 크고, 작으므로 swap 시킨다

3) 1)과 마찬가지

4) left와 right가 만나서 'left <= right' 조건에 의해 10에서 자기 자신을 swap 한다.

5) 'left > right'가 되어 while문을 빠져나오고, divide 함수의 결과로 left가 반환되어 newLeft가 된다. 이후 재귀적으로 quickSort 함수가 실행된다. 분해된 배열 arr의 길이가 1인 지점에서 base case로 재귀 실행이 멈추고, 최종적으로 정렬된 배열이 return 된다.

---

3. 시간복잡도

시간복잡도는 위에서 설명한 바와 같이 최악의 경우 O(N^2), 평균적으로는 O(NlogN)이 된다. 아래 참조2)의 영상을 보면 좋다. 간단하게 요약해보면,

 

1) 최악의 경우 : pivot 포인트를 잡을 때마다 배열에서 최소값 또는 최대값이 잡힌다. 예를 들어 최소값인 1이 pivot으로 잡히면, 배열의 다른 모든 요소들과 비교하는 N번의 과정이 걸린다. 이후 다음 최대값인 9가 pivot으로 잡히면, 다시 N번 비교를 반복한다. 각 단계에서 배열이(자료가) '1과 나머지 N-1개', '9와 나머지 N-2개' ...으로 나뉘어 N번 반복될 것이므로 N * N이 되어 O(N^2)이 된다.

 

2) 평균적인 경우 : pivot 포인트를 잡는 경우는 '1) 최악의 경우'와 마찬가지로 N번 반복된다. 다시 말해서 base case인 arr.length === 1이 될때까지 재귀반복이 진행되므로, N번의 실행이 요구되는 것이다. 그러나 각 실행마다 배열의 크기가(자료의 크기가) 평균적으로 반토막 나게 될 것이므로, logN의 시간복잡도를 갖게됨을 알 수 있다. 따라서 N * logN이 되어 O(NlogN)이 된다.

 

---

4. 참조

 

1) Code Playground - 퀵 정렬, 자바스크립트로 구현하기

im-developer.tistory.com/135

 

2) 유튜브 엔지니어대한민국 - [자료구조 알고리즘] 퀵정렬(Quicksort)에 대해 알아보고 자바로 구현하기

www.youtube.com/watch?v=7BDzle2n47c