[c++] 퀵 정렬

12 Dec 2023

퀵 정렬(Quick Sort)은 매우 효율적인 정렬 알고리즘 중 하나로, 평균적으로 O(n log n)의 시간 복잡도를 갖습니다.

#include <iostream>
using namespace std;

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  }

  if (left < j)
    quickSort(arr, left, j);
  if (i < right)
    quickSort(arr, i, right);
}

int main() {
  int arr[] = {5, 3, 8, 4, 2, 7, 1, 10, 6, 9};
  int n = sizeof(arr)/sizeof(arr[0]);

  quickSort(arr, 0, n - 1);

  cout << "Sorted array: ";
  for (int i=0; i<n; i++)
    cout << arr[i] << " ";
  return 0;
}

위의 코드는 C++로 구현된 기본적인 퀵 정렬 알고리즘입니다. 이 코드는 배열을 정렬하는 과정을 보여줍니다.

퀵 정렬에 대한 자세한 내용은 GeeksforGeeks를 참조하세요.

이렇게 퀵 정렬은 C++에서 구현하면 위와 같습니다.