[JS] 퀵 정렬

1. 퀵 정렬

 "퀵"이라는 말 그대로 정말 정말 정말 빠른 정렬이다.

 

 퀵 정렬은 특별한 경우를 제외하고는 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다.

 

 따라서 퀵 정렬의 시간 복잡도는 $$ O(N\times log_2{N}) $$ 이다.

 

 여태 포스팅했던 선택 정렬, 버블 정렬, 삽입 정렬의 시간 복잡도는 $$ O(N^2) $$ 이다.

 

 고등학교 수학을 배운 사람이라면 $$ N^2 > N \times log_2{N} $$ 이 성립된다는 것을 알 수 있다.

 

 하지만, 빅오 표기법에서 log₂N과 N²의 차이는 어느정도일까?

 

 차이는 어마무시하다고 말할 수 있다.  $$ N=2^{10} $$ 일 때를 예로 들어보자.

 

 2를 10번 곱하면 1024이다. 하지만 컴퓨터에서는 1024라고 하지 않고 통상 1000이라고 말한다.

 

 따라서 N을 1024가 아닌 1000이라고 두겠다.

 

 N이 1000일 때, N²은 1000 X 1000 =  1,000,000, 백만이다.

 

 따라서 O(N²)이라는 빅오표기법에 이를 적용하면 연산을 백만번 수행한다는 얘기가 된다.

 

 하지만

 

 log₂N의 경우에는? 1000은 2의 10승이기 때문에 10이 된다. 

 

 심지어 백만을 넣는다 하더라도 20이라는 어마무시한 숫자가 나온다.

 

 20과 백만의 차이는 어마무시하다. 이 차이를 보면 O(log₂N) 이 얼마나 빠른지 체감할 수 있을 것이다.

 

2. 동작 순서

 퀵 정렬은 분할과 정복이라는 작업을 반복수행하여 완성한다.

 

 분할은 정렬할 자료들을 기준값(피벗)을 중심으로 2개의 부분집합으로 분할하는 것을 의미하는다.

 

 이때 사용하는 기준값을 우리는 피벗이라고 부른다. 

 

 피벗은 일반적으로 첫 번째 값을 임의로 설정한다.

 

 정복은 기준 값보다 작은 원소들은 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다.

 

 그리고 부분집합의 크기가 1이하가 되면 퀵 정렬을 종료한다.

 

 이제 예시를 보여주려고 한다.

  

 여느 때와 같이 전에 포스팅했던 입력 예제를 가져와서 설명하려고 한다.

 

[그림 1] 입력 예제

 

 우리는 첫 번째 값 5를 피벗(기준 값)으로 주고 10에서 6까지 탐색을 한다.

 

[그림 2] 피벗 5, 초록색 배경: 탐색 범위

   

그리고 탐색을 하면서 5보다 작은 값은 LEFT에 넣고, 5보다 큰 값을 RIGHT에 넣는다.

 

 

[그림 3] 분할 작업

 

   이제 LEFT, RIGHT의 첫 번째 값을 피벗(기준 값)으로 설정하고 같은 작업을 재귀적으로 반복하면 된다.

 

 

[그림 4] 재귀적 반복

3. 시간 복잡도

 복잡도는 퀵 정렬이 다른 정렬보다 월등한 성능을 보이는 것은 사실이다.

 

 하지만, 특별한 경우가 있다.

 

 바로 정렬되어 있는 경우를 또 정렬하는 경우이다.

 

 [1, 2, 3, 4]를 예로 들어보자.

 

 1을 피벗으로 두고, LEFT, RIGHT로 나누면 (4번 연산) 

 

 LEFT는 비어있고, RIGHT에는 [ 2, 3, 4] 이 형성된다.

 

 [2, 3, 4]를 또 나누면 (3번 연산)

 

 LEFT는 비어있고, RIGHT에는 [3, 4] 이 형성된다.

 

 이렇게 연산을 하다보면 4 + 3 + 2 + 1의 연산횟수가 나오고, 이는 $$ O(n^2) $$ 이라는 속도가 나오게 된다.

 

 이 경우에는 오히려 퀵 정렬보다 삽입 정렬이 빠르다.

 

 따라서 정렬은 어느 것이 무조건 빠르다는 없는 것 같다. 

 

 결론은 상황을 보면서 유두리있게 사용을 하는 걸로...

 

4. 프로그램 코드

 퀵정렬의 코드는 다음과 같다.

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

 

5. 참고 자료

1. 동빈나 님의 블로그 - 5. 퀵 정렬

2. 조원호의 행복공간 님의 블로그 - [자바스크립트] 알고리즘 (Quick Sort, 퀵 정렬)

3. 자바로 배우는 쉬운 자료구조