13장 속도를 높이는 재귀 알고리즘

김현수·2022년 2월 22일

누구나 자료 구조와 알고리즘 알고리즘

누구나 자료 구조와 알고리즘

목록 보기

13/20

컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘은 퀵 정렬이다. 퀵 정렬은 매우 빠른 정렬 알고리즘이다. 특히 평균 시나리오에서 효율적이다.

퀵 정렬의 동작 방식을 공부하면 재귀를 사용해 어떻게 알고리즘의 속도를 크게 향상시키는지 배울 수 있다.

13.1 분할

배열을 분할한다는 것은, 배열로부터 임의의 수(피벗)를 가져와 피벗보다 작으면 왼쪽에, 피벗보다 크면 오른쪽에 두는 것이다.

배열 [0, 5, 2, 1, 6, 3]에서, 3을 임의로 피벗으로 한다. 포인터 두 개를 사용해, 한 포인터는 배열의 첫 번째 원소(0)에, 다른 한 포인터는 피벗을 제외한 가장 오른쪽 원소(6)에 할당한다.

왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮긴다. 피벗보다 크거나 같은 값에 도달하면 멈춘다.
오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮긴다. 피벗보다 작거나 같은 값에 도달하면, 또는 배열의 맨 앞에 도달하면 멈춘다.
오른쪽 포인터가 멈춘 후에는 둘 중 하나를 선택한다.
1. 왼쪽 포인터가 오른쪽 포인터에 도달하거나 넘어섰을 경우 4단계로 넘어간다.
2. 그렇지 않을 경우 왼쪽 포인터와 오른쪽 포인터가 가리키는 값을 교환한 후 1~3단계를 반복한다.
끝으로 왼쪽 포인터가 현재 가리키고 있는 값을 피벗과 교환한다.

위의 배열([0, 5, 2, 1, 6, 3])을 예시로 직접 적용해보면 다음과 같다.

왼쪽 포인터(0)와 피벗(3)을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
왼쪽 포인터(5)와 피벗을 비교한다. 피벗보다 크므로 왼쪽 포인터 이동을 멈춘다.
오른쪽 포인터(6)와 피벗을 비교한다. 피벗보다 크므로 다음 단계에서 오른쪽 포인터를 옮긴다.
오른쪽 포인터 (1)와 피벗을 비교한다. 피벗보다 작으므로 오른쪽 포인터를 멈춘다.
왼쪽 포인터(5)가 오른쪽 포인터에 도달하거나 넘어서지 않았으므로, 왼쪽 포인터와 오른쪽 포인터가 가리키는 값을 교환한다. [0, 1, 2, 5, 6, 3]
다음 단계에서 왼쪽 포인터를 이동한다.
왼쪽 포인터(2)와 피벗을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
왼쪽 포인터(5)와 피벗을 비교한다. 피벗보다 크므로 왼쪽 포인터 이동을 멈춘다.
왼쪽 포인터와 오른쪽 포인터가 같은 값을 가리키므로 포인터 이동을 중지한다.
분할의 마지막 단계로 왼쪽 포인터와 피벗을 교환한다. [0, 1, 2, 3, 6, 5].

정렬되진 않았지만 3을 피벗으로 배열이 분할됐다. 3은 이제 배열 내에 올바른 위치에 있다.

13.1.1 코드 구현: 분할

class SortableArray {
  constructor(array) {
    this._array = [...array];
  }

  partition(leftPointer, rightPointer) {
    // 항상 가장 오른쪽 값을 피벗으로 선택한다.
    // 나중에 사용할 수 있도록 피벗의 인덱스를 저장한다.
    const pivotIndex = rightPointer;
    const pivot = this._array[pivotIndex];

    // 피벗 바로 왼쪽에서 오른쪽 포인터를 시작시킨다.
    rightPointer -= 1;

    while (true) {
      while (this._array[leftPointer] < pivot) {
        // 피벗보다 크거나 같은 값을 가리킬 때까지 왼쪽 포인터를 오른쪽으로 옮긴다.
        leftPointer += 1;
      }
      while (this._array[rightPointer] > pivot) {
        // 피벗보다 작거나 같은 값을 가리킬 때까지 오른쪽 포인터를 왼쪽으로 옮긴다.
        rightPointer -= 1;
      }

      // 왼쪽 포인터와 오른쪽 포인터가 모두 이동을 멈췄다.
      if (leftPointer >= rightPointer) {
        // 왼쪽 포인터가 오른쪽 포인터에 도달했거나 넘어섰다면 반복문을 빠져나간다.
        break;
      } else {
        // 왼쪽 포인터가 오른쪽 포인터보다 앞에 있다면 둘의 값을 교환한다.
        [this._array[leftPointer], this._array[rightPointer]] = [
          this._array[rightPointer],
          this._array[leftPointer],
        ];
        // 다음 번 왼쪽 포인터와 오른쪽 포인터의 이동을 위해 왼쪽 포인터를 옮긴다.
        leftPointer += 1;
      }
    }

    // 분할의 마지막 단계로 왼쪽 포인터의 값과 피벗을 교환한다.
    [this._array[leftPointer], this._array[pivotIndex]] = [
      this._array[pivotIndex],
      this._array[leftPointer],
    ];
    // 다음 예제에 나올 퀵 정렬 메서드를 위해 왼쪽 포인터를 반환한다.
    return leftPointer;
  }
}

partition 메서드는 왼쪽 포인터와 오른쪽 포인터의 시작점을 인자로 받는다. 처음 호출하면 배열의 왼쪽 끝과 오른쪽 끝을 가리킨다. 하지만 퀵 정렬은 배열 전체가 아닌, 일부분에 대해서도 분할 메서드를 호출하므로, 포인터를 인자로 받아야 한다.

피벗은 항상 처리하는 범위 내 가장 오른쪽 원소다.
피벗을 결정하면 오른쪽 포인터를 피벗 바로 왼쪽 항목으로 옮긴다.

이어서 포인터가 만날 때까지 실행되는 반복문을 실행한다. 왼쪽 포인터는 피벗보다 크거나 같은 항목에 도달할 때까지 오른쪽으로, 오른쪽 포인터는 피벗보다 작거나 같은 항목에 도달할 때까지 왼쪽으로 옮긴다.

두 포인터가 이동을 멈추면 두 포인터가 마주쳤는지 확인하고, 마주쳤으면 반복문을 종료한다. 마주치지 않았다면 두 포인터의 값을 교환한다.

두 포인터가 마주쳤으면 반복문을 종료하고 왼쪽 포인터의 값과 피벗을 교환한다.

13.2 퀵 정렬

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

배열을 분할한다. 피벗이 올바른 위치에 있다.
피벗의 왼쪽, 피벗의 오른쪽을 각각의 배열로 보고 1단계와 2단계를 재귀적으로 반복한다.
하위 배열의 원소가 0개 혹은 1개라면 기저 조건이므로 아무 것도 하지 않는다.

앞서 분할을 통해 [0, 1, 2, 3, 6, 5]를 얻었다. 피벗 왼쪽은 정렬되어 있지만 컴퓨터는 아직 모른다.

분할이 끝나면 피벗 왼쪽의 모든 값을 하나의 배열로 보고([0, 1, 2]), 피벗을 2로 설정하고 분할한다.

13.1의 8단계에 이어 진행한다.

왼쪽 포인터(0)와 피벗을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
왼쪽 포인터(1)와 피벗을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
왼쪽 포인터는 피벗을 가리킨다. 피벗과 같은 값을 가리키므로 왼쪽 포인터를 멈춘다.
오른쪽 포인터(1)와 피벗을 비교한다. 피벗보다 작으므로 오른쪽 포인터를 멈춘다.
왼쪽 포인터(2)가 오른쪽 포인터(1)를 지나쳤다. 더 이상 포인터를 이동시키지 않는다.
피벗과 왼쪽 포인터의 값을 교환한다. 왼쪽 포인터가 가리키는 값이 피벗이므로, 아무런 변화 없다. 피벗 2는 올바른 위치에 있다. [0, 1, 2]

피벗 2 왼쪽에는 [0, 1]이라는 하위 배열이 있고, 오른쪽에는 아무런 하위배열이 없다. 하위배열 [0, 1]을 재귀적으로 분할한다.

피벗이 1이므로, 왼쪽 포인터와 오른쪽 포인터가 모두 0을 가리킨다.

왼쪽 포인터(0)와 피벗을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
왼쪽 포인터는 피벗을 가리킨다. 피벗과 같은 값을 가리키므로 왼쪽 포인터를 멈춘다.
오른쪽 포인터(0)와 피벗을 비교한다. 피벗보다 작으므로 오른쪽 포인터를 멈춘다.
왼쪽 포인터가 오른쪽 포인터를 지나쳤다. 더 이상 포인터를 이동시키지 않는다.
피벗과 왼쪽 포인터의 값을 교환한다. 왼쪽 포인터가 가리키는 값이 피벗이므로, 아무런 변화 없다. 피벗 1는 올바른 위치에 있다. [0, 1]

이제 하위 배열은 [0]이다. 원소가 0개 혹은 1개인 배열은 기저 조건이므로 아무것도 하지 않고, 올바른 위치에 있다고 간주된다.

3의 오른쪽에 있는 하위 배열인 [6, 5]를 재귀적으로 분할한다. 피벗은 5이고, 포인터는 둘 다 6을 가리킨다.

왼쪽 포인터(6)와 피벗을 비교한다. 피벗보다 크므로 왼쪽 포인터 이동을 멈춘다.
오른쪽 포인터(6)와 피벗을 비교한다. 피벗보다 크므로 이동시켜야 한다. 하지만 배열의 맨 앞 요소이므로 이동을 할 수 없다. 이동을 멈춘다.
두 포인터가 만났으므로 더 이상 포인터를 이동시키지 않는다.
피벗과 왼쪽 포인터의 값을 교환한다. 피벗 5은 올바른 위치에 있다. [5, 6]

하위 배열 [6]은 기저 조건에 해당하므로 아무것도 하지 않고, 올바른 위치에 있다고 간주된다.

정렬이 완료 됐다. [0, 1, 2, 3, 5, 6]

13.2.1 코드 구현: 퀵 정렬

quicksort(leftIndex, rightIndex) {
    // 기저 조건: 하위 배열의 원소가 0개 혹은 1개일 때
    if (rightIndex - leftIndex <= 0) {
      return;
    }

    const pivotIndex = this.partition(leftIndex, rightIndex);
    this.quicksort(leftIndex, pivotIndex - 1);
    this.quicksort(pivotIndex + 1, rightIndex);
  }

quicksort 함수를 SortableArray의 메서드로 추가한다.
메서드를 실행하면 처음으로 leftIndex와 rightIndex 사이의 원소들을 분할한다. 이때 partition 메서드의 반환값을 pivotIndex에 할당한다.

이어서 피벗의 왼쪽, 오른쪽 하위 배열에 quicsort메서드를 재귀적으로 호출한다.

13.3 퀵 정렬의 효율성

퀵 정렬의 효율성을 알아내려면 한 번 분할할 때 효율성을 밝혀야 한다.
분할에 필요한 단계에는 값과 피벗을 비교하는 비교와, 왼쪽과 오른쪽 포인터가 가리키는 값을 교환하는 교환으로 두 종류가 있다.

각 분할마다 배열 내 원소를 피벗과 비교하므로 최소 N번 비교한다. 분할 한 번마다 왼쪽, 오른쪽 포인터가 만나야하기 때문이다.

교환 횟수는 데이터가 어떻게 정렬되어 있느냐에 따라 다르다.
모두 교환해야 한다는 최악의 시나리오를 고려하면 한 분할에서 최대 N/2번 교환한다.
대부분은 매번 교환이 일어나진 않으므로, 반 정도만 교환된다고 가정하면 평균 N/4번 교환한다고 알 수 있다.

따라서 N + 0.25N = 1.25N 단계이므로 분할에는 O(N)이 걸린다.
하지만 이것은 분할 1회의 효율성이고, 퀵 정렬은 분할을 여러 번하므로 퀵 정렬의 효율성을 알아내려면 좀 더 분석해야 한다.

13.3.1 한눈에 보는 퀵 정렬

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

O O O O O O O O
O O O V X X X X
O V X V X X X X
V V O V X X X X
V V V V O O O O
V V V V O O V X
V V V V V O V X
V V V V V V V O

O는 분할하는 원소들, V는 올바른 위치에 자리한 원소, X는 분할에 포함되지 않는 원소들이다.
8개 원소를 퀵 정렬하는데 하위 배열의 원소를 모두 합했더니 21개이므로, 약 21단계가 걸렸다고 할 수 있다.
원소가 16개라면 약 64단계가 걸리고, 32개라면 약 160단계가 걸린다.

13.3.2 빅 오로 나타낸 퀵 정렬

배열의 원소가 N개라면 퀵 정렬에 필요한 단계 수는 약 N * logN이다.

평균적으로 피벗을 배열 중간 어딘가로 가정하면, 배열을 나눌 때마다 두 하위 배열은 크기가 비슷할 것이다.
N개의 원소를 가진 배열을 크기가 1이 될 때까지 계속 반으로 나누려면 logN번 걸린다.
각 분할은 약 N단계가 걸리므로 퀵 정렬에는 N * logN 단계가 걸린다.

13.4 퀵 정렬의 최악의 시나리오

퀵 정렬의 최선의 시나리오는 분할 후 피벗이 하위 배열의 가운데 있을 때다. 최악의 시나리오는 피벗이 항상 하위 배열의 한쪽 끝에 있을 때다. 배열이 완전히 오름차순 혹은 내림차순일 때 일어난다.

최악의 시나리오에서는 각 분할마다 교환은 한 번뿐이지만 비교가 너무 많다. 8개의 원소를 가진 최악의 시나리오에서 퀵 정렬은 8 + 7 + 6 + ... + 1개의 요소를 분할하고, 총 36번 비교한다.

즉, N + (N-1) + (N-2) + ... + 1단계가 걸리고 이는 N²/2 단계이므로, 최악의 시나리오에서 퀵 정렬은 O(N²)이다.

13.4.1 퀵 정렬 대 삽입 정렬

퀵 정렬 대 삽입 정렬을 비교해 보자.

최악의 상황일 땐 둘 다 O(N²)로 동일하다.
최선의 상황일 땐 삽입 정렬이 O(N)으로 O(N logN)인 퀵 정렬 보다 빠르다.

하지만 평균적인 경우에 삽입 정렬은 O(N²)이 걸리는 반면 퀵 정렬은 훨씬 더 빠른 O(N logN)이 걸린다.

13.5 퀵 셀렉트

무작위로 정렬된 배열이 있을 때, 정렬은 안 해도 되지만 배열에서 특정한 인덱스의 값을 알고 싶다. 이 때 전체 배열을 정렬한 후 적절한 인덱스를 바로 찾아보면 이 문제를 풀 수 있다. 하지만 퀵 정렬을 사용하더라도 평균 O(N logN)이 걸릴 것이다.

퀵 셀렉트를 사용하면 더 나은 성능을 낼 수 있다. 퀵 셀렉트도 분할에 기반하며, 퀵 정렬과 이진 검색의 하이브리드 정도로 생각할 수 있다.

퀼 셀렉트는 분할 후 피벗이 배열 내 올바른 위치에 있다는 점을 이용한다.

값이 8개인 배열에서 2번째로 작은 값을 찾는다고 했을 때, 분할 후 피벗이 5번 셀에 위치한다면, 그 배열의 5번째로 작은 값을 알아낸 것이다. 2번째로 작은 값은 5번 셀보다는 왼쪽에 있을 것이므로, 왼쪽 하위 배열에만 집중하면 된다.

즉, 전체 배열을 정렬하지 않고도 올바른 값을 찾을 수 있다.

13.5.1 퀵 셀렉트의 효율성

퀵 셀렉트는 평균 시나리오에서 O(N)이다. 원소가 N개 일 때 N + (N/2) + (N/4) + ... + 2단계이고, 이는 약 2N단계 이므로 O(N)이다.

13.5.2 코드 구현: 퀵 셀렉트

quickSelect(kthLowestValue, leftIndex, rightIndex) {
  // 기저 조건이면, 즉 하위 배열에 셀이 하나면 찾고 있던 값을 찾은 것이다.
  if (rightIndex - leftIndex <= 0) {
    return this._array[leftIndex];
  }

  // 배열을 분할하고 피벗의 위치를 가져온다.
  const pivotIndex = this.partition(leftIndex, rightIndex);

  if (kthLowestValue < pivotIndex) {
    // 찾으려는 인덱스가 피벗의 인덱스보다 작으면 왼쪽 하위배열에만 실행
    return this.quickSelect(kthLowestValue, leftIndex, pivotIndex - 1);
  } else if (kthLowestValue > pivotIndex) {
    // 찾으려는 인덱스가 피벗의 인덱스보다 크면 오른쪽 하위배열에만 실행
    return this.quickSelect(kthLowestValue, pivotIndex + 1, rightIndex);
  } else {
    // 찾으려는 인덱스가 피벗의 인덱스와 같으면 값을 찾은 것
    return this._array[pivotIndex];
  }
}

quickSelect 함수를 SortableArray 클래스의 메서드로 추가한다.

두 번째로 작은 값을 찾고 싶다면 다음과 같이 입력한다.

let array = new SortableArray([0, 5, 2, 1, 6, 3]);
console.log(array.quickSelect(0, 1, array._array.length - 1));

13.6 다른 알고리즘의 핵심 역할을 하는 정렬

현재까지의 가장 빠른 정렬 알고리즘의 속도는 O(N lonN)이다.
퀵 정렬이 가장 유명하나 병합 정렬 역시 O(N logN)이다.

4장에서 다뤘던 배열에 중복이 있는지 확인하는 문제에서, 정렬을 이용해 O(N²)인 이차 해법을 개선할 수 있다.

중복이 있는 배열 [5, 9, 3, 2, 4, 5, 6]을 정렬하면 [2, 3, 4, 5, 5, 6, 9]가 된다. 정렬된 배열을 순회하며 다음 숫자와 동일한지 판단하면 중복을 찾을 수 있다.

function hasDuplicateValue(array) {
  array.sort((a, b) => (a < b ? -1 : 1));
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] === array[i + 1]) {
      return true;
    }
  }
  return false;
}

이 알고리즘은 정렬을 하나의 컴포넌트로 사용한다.

자바스크립트 내 sort() 함수의 효율성을 O(N logN)이라고 가정하면, 정렬한 후 N단계에 걸쳐 배열을 순회했으므로 N logN + N단계가 걸린다. 따라서 O(N logN)이다.

많은 알고리즘에서 정렬을 더 큰 프로세스의 일부로 사용한다.

13.7 마무리

퀵 정렬과 퀵 셀렉트는 이해하긴 어렵지만 깊은 생각 끝에 나온 알고리즘이 얼마나 성능을 높일 수 있는지 보여준다.

김현수

이전 포스트

12장 동적 프로그래밍

다음 포스트