[알고리즘] 퀵 정렬 (Quick Sort)

퀵정렬이란?

퀵 정렬은 기준점을 획득한 다음 해당 기준점을 기준으로 배열을 나눈다. 한 쪽에는 기준점보다 작은 항목들이 위치하고 다른 쪽에는 기준점보다 큰 항목들이 위치한다. 나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 정렬이 완료된다.

❓ 기준점을 정하는 방법이 따로 있을까 ?
👉 보통은 정렬할 배열의 첫번째 원소, 마지막 원소, index가 중앙값인 원소를 기준점으로 정한다.

퀵정렬 알고리즘

분할 ➡ 정복 ➡ 결합

• 분할 (Divide)
  정렬할 배열을 기준점을 기준으로 2개의 부분배열로 분할한다.
• 정복 (Conquer)
  부분 배열을 정렬한다.
• 결합 (Combine)
  정렬된 부분 배열들을 하나의 배열에 합병한다.

❓ 무한루프가 도는 상황이 있나?
👉 순환 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

시간복잡도

• 평균 : O(nlog₂n)
• 최악 : O(n^2)

❓ 퀵정렬이 정렬중에 가장 빠른 알고리즘으로 알려져 있는데 모든 상황에서 유리할까?

예시 ) 정렬되어 있는 경우를 또 정렬하는 경우
[1,2,3,4] 인 배열이 있을 때 1을 기준점으로 두고 두 개의 부분배열로 나누면 4번의 연산이 필요하다. 현재 1보다 작은 배열은 없는 상태이고 큰 배열엔 [2,3,4]가 있으므로 [2,3,4]를 또 나누면 3번의 연산이 필요 ...
이렇게 총 4+3+2+1로 O(n^2)의 시간복잡도를 갖게 된다.

👉 이러한 경우 퀵 정렬보다 삽입 정렬이 빠르다.

최악의 시간복잡도를 방지하기 위한 방법

1. 랜덤화
   배열의 랜덤한 두 개의 index를 뒤바꾸어주는 방식으로 배열이 정렬되어 있지 않도록 만든다.

2. 랜덤 기준점 선택
   기준점을 난수를 발생시켜 선택하는 방법으로, 정렬되었거나, 정렬에 가까운 배열에서 최악을 선택하는 횟수가 적어질 것이다.

3. Median Of Three Pivot
   기준점을 선택할 때 3개의 원소를 후보로 두고 그 중간 값을 선택하는 방법으로 이렇게 기준점을 선택하면 최악의 경우는 반드시 피할 수 있다.

퀵정렬 예시

퀵정렬 코드

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));
}