알고리즘 - 퀵 정렬 (Quick Sort) / 퀵 정렬 구현

분할이란?

---

퀵 정렬은 분할이라는 개념에 기반한다. 배열은 분할한다는 의미는 배열로부터 임의의 수를 가져와 피벗보다 작은 모든 수는 피벗의 왼쪽에 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 여기서 피벗(pivot)은 배열로부터 가져온 임의의 수를 의미한다.

 

📌 분할 알고리즘 순서

* 가장 오른쪽에 있는 수를 피벗으로 정했을 때.

1. 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.
3. 오른쪽 포인터가 멈춘 경우
   • 왼쪽 포인터가 오른쪽 포인터에 도달했으면 4단계로 넘어간다.
   • 그렇지 않으면 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한 후 1-3단계를 반복한다.
4. 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환한다.

 

퀵 정렬

---

🔑 keyword : 랜덤 정렬

 

퀵 정렬은 분할 정복 방식으로 정렬을 수행하는 알고리즘이다. 배열을 부분 배열로 분할한 다음에 각각의 부분 배열을 독립적으로 정렬한다. 퀵 정렬의 장점은 추가적인 메모리를 사용하지 않고 입력 배열의 메모리 안에서 즉석으로 정렬되며 다른 정렬 알고리즘과 비교했을 때 가장 짧은 내부 루프를 가진다. 또한, 퀵 정렬은 구현하기 쉽고 다양한 형태의 입력 데이터들에도 잘 동작하며 전형적인 응용 상황에서 다른 정렬 알고리즘보다 훨씬 빠른 성능을 가지고 있다. 퀵 정렬의 동작 방식을 학습하여 재귀를 사용해 어떻게 알고리즘의 속도를 크게 향상시키는지 배울 수 있고 다른 실용적인 알고리즘에도 똑같이 적용할 수 있다.

 

📌 퀵 정렬의 동작 순서

퀵 정렬 알고리즘은 분할과 재귀로 이루어진다.

1. 배열을 분할한다.
2. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 다른 배열로 보고 1-2단계를 재귀적으로 반복한다.
3. 하위 배열이 원소를 0개 혹은 1개 포함하면 재귀의 종료 조건으로 종료된다.

 

📌 퀵 정렬의 효율성

퀵 정렬에서 분할에는 비교와 교환, 두 가지 단계를 포함하고 있다.

• 비교 : 각 값과 피벗을 교환한다.
• 교환 : 적절한 때에 왼쪽과 오른쪽 포인터가 가리키고 있는 값을 교환한다.

 

퀵 정렬은 기본적으로 연이은 분할로 수행되는데 각 분할마다 하위 배열의 원소가 N개일 때 약 N단계가 걸린다. 그리고 모든 하위 배열의 크기를 합하면 퀵 정렬에 걸리는 총 단계 수가 나온다. 원소의 개수에 따른 퀵 정렬 단계 수이다.

 

N	퀵 정렬 단계 수 (근사치)
4	8
8	24
16	64
32	160

 

위 표를 확인해 보면 퀵 정렬에 필요한 단계 수는 약 NxlogN단계로 퀵 정렬의 효율성은 O(NlogN)이다.

 

📌 최악의 경우

최악의 경우는 피벗이 하위 배열의 정중앙이 아닌 한쪽 끝에 있는 경우이다. 보통 배열이 오름차순이거나 내림차순일 때이다. 이 경우 원소가 N개일 때 N + (N-1) + (N-2) + (N-3) ... +1 단계가 걸리고 효율성은 O(N^2)이다.

 

📌 최선의 경우

분할 후 피벗이 하위 배열의 한가운데 있을 때 이다.

 

📌 평균의 경우

배열이 무작위로 정렬된 평균적인 상황에는 대략 값의 반 정도만 교환한다. 그래서 평균적으로 logN번 반으로 나누고 나눌 때마다 모든 하위 배열에 대해 분할을 수행하는 데 그 하위 배열의 원소 수를 모두 합하면 N이다. 그래서 평균적인 경우에서 효율성은 O(NlogN)이다.

 

	최선의 경우	평균의 경우	최악의 경우
퀵 정렬	O(NlogN)	O(NlogN)	O(NlogN)

 

퀵 정렬이 삽입 정렬보다 우수한 이유는 평균적인 경우에서의 차이 때문이다. 역순으로 정렬된 배열이 주어지는 최악의 상황에서는 삽입 정렬이나 선택 정렬과 성능이 비슷하지만 평균적인 상황에서는 훨씬 빠르다.

 

Ex.

const shuffle = (array) => {
  let randomIndex;

  for (let i = array.length; i > 0; i--) {
    randomIndex = Math.floor(Math.random() * i);
    i--;

    [array[i], array[randomIndex]] = [array[randomIndex], array[i]];
  }
};


const exchange = (array, low, high) => {
  [array[high], array[low]] = [array[low], array[high]];
}

const less = (a, b) => a < b;

const patition = (array, low, high) => {
  let left  = low + 1,
      right = high;

  const pivot = array[low];

  while(true){
    while(less(array[left], pivot)){
      if(left === high) break;

      left++;
    }

    while(less(pivot, array[right])){
      if(right === low) break;

      right--;
    }

    if(left >= right) break; // 가리키는 요소가 겹칠 때
    exchange(array, left, right);
  }

  exchange(array, low, right);
  return right;
}

const sort = (array, low, high) => {
  if(low >= high) return;

  const index = patition(array, low, high);
  sort(array, low, index - 1);
  sort(array, index + 1, high);
}

const quickSort = (array) => {
  shuffle(array); // 배열 무작위로 섞음
  sort(array, 0, array.length - 1);
};

 

퀵 셀렉트

---

퀵 셀렉트도 분할에 기반하며 퀵 정렬과 이진 검색의 하이브리드 버전이라고 할 수 있다. 분할이 끝나면 피벗 값을 배열 내 올바른 위치에 있다는 것을 이용한다. 배열을 계속 반으로 나누면서 찾고 있는 값이 있을 반쪽만 분할해 가면 된다. 퀵 셀렉트의 장점은 전체 배열을 정렬하지 않고도 올바른 값을 찾을 수 있다는 점이다.

 

📌 퀵 셀렉트의 효율성

각 분할이 일어날 때마다 분할 중인 하위 배열에 대해 N단계가 걸린다. 원소가 N개인 배열에서 N + (N/2) + (N/4) + (N/8) + ... 2단계가 걸린다. 대략 2N단계가 걸리기 때문에 효율성은 O(N)이다.