[자료구조/C++] 정렬 (Sorting) : 퀵정렬 (Quick Sort)

전공 수업과 교안을 바탕으로 개인적으로 공부한 내용입니다. 공부 내용을 정리하는 과정에서 잘못된 정보가 있을 수 있으니, 참고용으로만 봐주시면 감사하겠습니다. 피드백은 언제든 환영입니다! 😊

---

✔️ 퀵정렬 (Quick Sort)

퀵정렬은 분할정복 (Divide and Conquer) 알고리즘 중 하나로, 평균적으로 빠른 실행 속도를 갖는 정렬 알고리즘이다.

(분할 정복 알고리즘은, 큰 문제를 작은 하위 문제로 분할하여 독립적으로 해결한 후, 해결한 것들을 결합하여 전체 문제를 해결하는 방법론을 말한다) 퀵 정렬 알고리즘은 재귀적으로 접근하여 구현할 수 있으며 구현 방법은 다음과 같다.

 

우선, 퀵 정렬에서 기준이 되는 피벗(pivot) 를 설정하고, 피벗을 기준으로 배열을 두 개의 부분 배열로 분할한다.

분할한 배열에서 피벗보다 작거나 같은 원소는 왼쪽 부분 배열로, 큰 원소는 오른쪽 배열 부분으로 이동시키며 이러한 과정을 피벗를 중심으로 반복하여 부분 배열들을 만든다. 따라서 부분 배열의 크기가 하나 이하의 원소를 갖는 경우, 정렬을 중단하고 재귀 호출을 종료시킨다.

 

이때, 퀵정렬에서 피벗의 위치를 구하는 방법은 다음과 같다.

 

먼저 배열의 첫번째 인덱스를 피벗로 설정한다.

(피벗을 꼭 배열의 첫번째 인덱스 값으로 하지 않아도 된다. 단, 피벗이 어떤 값이냐에 따라 성능이 달라질 수 있다)

피벗을 기준으로 배열의 인덱스를 오름차순으로 이동하여 피벗보다 큰 값을 가지는 배열의 left 인덱스 값을 찾고, 배열의 맨 끝에서부터 배열의 인덱스를 내림차순으로 이동하여 피벗보다 작거나 같은 값을 가지는 배열의 right 인덱스 값을 찾는다. 배열의 인덱스를 이동시키면서 피벗보다 작은 left 인덱스 값과 피벗보다 큰 right 인덱스 값을 찾은 경우, 이 두 값을 교환하고 이러한 과정을 left 인덱스가 right 인덱스 보다 커질 때까지 반복한다.

따라서 만약 left 인덱스가 right 인덱스보다 커지는 경우, pivot으로 설정한 값과 right값을 교환하면 된다.

 

 

---

 

이해를 위해 다음 예시를 참고하자.

 

예를 들어 {30, 20, 40, 35, 5, 10, 45, 50, 25, 15, ∞} 로 구성된 배열 A가 있다고 하자.

(이때, 마지막 원소인 ∞는 dummy값이며, 피벗을 구할때 만약 기존의 배열이 내림차순으로 정렬 되어 있는 경우, 배열의 0번째 원소 값을 피벗으로 설정하면 피벗보다 큰 값이 존재하지 않게 되어 left 인덱스 값이 존재하지 않는 오류가 발생하므로 오류를 피하는 용도로  ∞를 dummy값으로 추가하였다)

 

먼저 피벗은 다음과 같은 과정으로 구할 수 있다.

 

 

위의 과정을 거쳐 피벗 값인 30의 위치를 구하면, 피벗 값 30을 기준으로 30보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 위치하게 된다.

 

동일한 방식으로 배열을 나누는 과정을 진행하면서 부분 배열들의 크기가 하나 이하의 원소를 갖게 되면 정렬을 중단하고 재귀 호출이 종료하여 퀵정렬을 마치면 된다.

 

따라서 퀵정렬을 코드를 구현하면 다음과 같다.

 

✔️ 구현 코드

#include <iostream>
#include <limits>
using namespace std;

void Swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

// 피벗(pivot) 위치 구하기
int Partition(int A[], int left, int right) {
  int pivot, value;
  pivot = left;
  value = A[pivot];

  do {
    while (A[++left] < value);
    while (A[--right] > value);

    if (left < right) {
      Swap(A[left], A[right]);
    } else {
      break;
    }
  } while (1);

  A[pivot] = A[right];
  A[right] = value;

  return right;
}

void QuickSort(int A[], int left, int right) {
  int k;

  if (left < right) {
    k = Partition(A, left, right+1);
    QuickSort(A, left, k-1);
    QuickSort(A, k+1, right);
  }
}

int main () {
  int dummy = numeric_limits<int>::max();
  int A[] = {30, 20, 40, 35, 5, 10, 45, 50, 25, 15, dummy};
  int size = sizeof(A)/sizeof(A[0]);

  QuickSort(A, 0, size-1);

  for (int i=0; i<size-1; i++) {
    cout << A[i] << " ";
  }
  cout << endl;

  return 0;
}