알고리즘 패턴: 퀵 정렬 (Quicksort), 퀵 선택 (Quickselect)

퀵 정렬은 파티션(partition)이라는 알고리즘을 사용해 배열을 정렬한다. Big-O 표기법으로는 많은 정렬 알고리즘과 동일하게 n²이지만, 평균적으로는 n * log(n) 정도의 시간복잡도를 가진다고 한다.

 

파티션

파티션 알고리즘에서는 말 그대로 배열을 부배열(subarray)이라는 파티션으로 나눈다. 이때 피벗(pivot)이라는 임의로 고른 원소의 좌우로 부배열이 나눠지게 된다. 좌측 부배열은 피벗보다 작거나 같은 값으로 이루어진 배열이고, 우측 부배열은 피벗보다 크거나 같은 값만 있는 배열이다.

 

파티션을 나누기 위해 먼저 전체 배열의 마지막 원소를 피벗으로 삼는다. 그런 다음 배열의 첫번째 인덱스부터 차례대로 피벗의 값과 비교하면서 정렬해나가는데, 이미 정렬된 부배열과 정렬해야 되는 부배열을 구분하기 위해 두가지의 인덱스를 사용한다. 인덱스 i를 좌측 부배열의 마지막 인덱스로 하고 인덱스 j를 아직 정렬되지 않은 부분의 첫번째 인덱스로 삼는다. i와 j 사이는 우측 부배열의 영역이 된다.

 

이제 0번째 인덱스부터 시작해 array[j] 값을 피벗과 비교한다. 피벗보다 크면 그대로 두고 j만 1씩 증가시키지만, 만약 더 작은 값일 경우 현재 j의 위치와 i + 1의 위치를 바꿔준다. i + 1인 이유는 피벗보다 작은 값을 찾을 때마다 좌측 부배열의 길이를 1씩 늘려야 하기 때문이다. (이미지 참고)

출처: Introduction to Algorithms, 4th ed.

 

위 작업은 피벗의 전 원소를 확인할 때까지 반복한다. 이렇게 배열의 원소들을 옮기다 보면 반복문이 끝났을 때 피벗을 제외한 원소들이 피벗보다 작거나 큰 값 둘 중 하나의 배열에 속하게 된다. 마지막으로 i + 1 인덱스와 피벗의 인덱스 자리를 바꾸면 피벗의 좌측에는 피벗보다 작은 값들이, 우측에는 피벗보다 큰 값들이 위치하게 된다.

function partition(arr, p, r) {
  let pivot = arr[r]; // 배열의 마지막 원소를 피벗으로 지정
  let i = p - 1; // i = 좌측 부배열의 마지막 인덱스 (처음에는 좌측 부배열이 존재하지 않음)

  for (let j = p; j < r; j++) {
    // arr[j] 값이 피벗보다 작을 경우 좌측 부배열의 마지막 위치와 자리 교환
    if (arr[j] < pivot) {
      i += 1;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]]; // 피벗을 좌측 부배열의 오른쪽으로 재배치
  return i + 1; // 피벗의 최종 위치
}

 

partition() 함수는 퀵 정렬 알고리즘 내에서 배열을 mutate하고 피벗이 최종적으로 위치한 인덱스 값을 리턴한다.

 

파티션 반복으로 배열 전체를 정렬

퀵 정렬은 파티션 알고리즘을 활용해 피벗 값의 좌우 부배열이 전부 정렬될 때까지 반복 순환하는 알고리즘이다. 합병 정렬처럼 문제를 분할 정복해서 점점 작아지는 규모의 부배열들을 정렬한다. 참고로 합병 정렬과는 다르게 퀵 정렬은 정렬된 작은 부배열들을 다시 정렬하면서 합칠 필요가 없다는 강점을 가진다.

 

p부터 r까지의 인덱스가 있는 배열 arr[p : r]의 p와 r이 같은 값이 아닌 이상(같은 값이라는 것은 원소가 하나라서 정렬할게 없다는 뜻이다), 파티션 함수 partition(arr, p, r)을 돌렸을 때 리턴하는 피벗값의 인덱스 q를 가지고 왼쪽 부배열 arr[p : q-1]과 오른쪽 부배열 arr[q+1 : r]을 정렬하는 것을 재귀 함수처럼 반복한다.

function quicksort(arr, p, r) {
  if (p < r) {
    let q = partition(arr, p, r);

    quicksort(arr, p, q - 1); // 왼쪽 정렬 반복
    quicksort(arr, q + 1, r); // 오른쪽 정렬 반복
  }
}

 

퀵 정렬을 응용한 원소 찾기

퀵 정렬에서 사용되는 파티션 로직은 정렬되지 않은 배열에서 n번째로 작은 원소를 찾을 때에도 유용하게 써먹을 수 있다.

 

n번째 원소는 마치 파티션 로직의 피벗과도 같다. 좌우 부배열들이 반드시 정렬되어 있진 않아도 피벗의 위치는 항상 좌측 부배열보다 나중에 오고, 우측 부배열보다 먼저 오기 때문에 절대적이다. n번째 원소를 찾을 때 나머지 원소들이 현재 정렬된 상태인지 아닌지는 중요하지 않으니 퀵 정렬을 해나가면서 피벗의 인덱스 값이 n인지만 찾으면 된다.

function quickselect(arr, p, r, n) {
  if (p <= r) {
    let q = partition(arr, p, r);

    if (q === n) {
      return arr[q]; // 인덱스 n이 피벗의 인덱스와 일치할 경우 n번째 원소를 찾은 것으로 판단할 수 있다
    } 
    else if (q > n) {
      // q가 n보다 크면 더 작은 피벗을 찾기 위해 왼쪽 정렬을 반복한다
      return quickselect(arr, p, q - 1, n);
    } 
    else {
      // q가 n보다 작으면 더 큰 피벗을 찾기 위해 오른쪽 정렬을 반복한다
      return quickselect(arr, q + 1, r, n);
    }
  }
  return null; // 뭔가가 잘못돼 n번째 원소를 찾을 수 없음
}

 

위와 같은 방식으로 특정 원소를 찾는 것을 퀵 선택이라고 한다.

 

아래는 퀵 선택을 시각화한 예제다. (k번째 원소를 찾는데 k가 통상적인 인덱스와 달리 1부터 시작하기 때문에 k - 1를 해줬다)

출처: CS Robot @ YouTube