[기초] C++ 알고리즘 : 퀵 정렬 (Quick Sort)

---

 

퀵 정렬(Quick Sort)은 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.

이 알고리즘은 분할 정복(Divide and Conquer) 방법을 기반으로 합니다.

기본 아이디어는 피벗(pivot) 요소를 선택하고 이를 기준으로 배열을 분할하고 정렬하는 것입니다.

평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우 O(n^2)입니다.

일반적으로 다음과 같은 단계로 진행됩니다:

 

• 피벗 선택
  배열에서 피벗(pivot) 요소를 선택합니다. 일반적으로는 첫 번째 요소, 마지막 요소, 중간 요소 등이 선택됩니다.
  
  
• 분할
  피벗을 기준으로 배열을 분할합니다.
  피벗보다 작은 요소는 피벗의 왼쪽에, 큰 요소는 오른쪽에 위치하도록 재배치합니다.
  
  
• 재귀적으로 정렬
  분할된 두 하위 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
  
  
• 합병
  재귀 호출을 통해 정렬된 두 하위 배열을 합병하여 최종 정렬된 배열을 생성합니다.

---

 

#include <iostream>

using namespace std;

// 피벗을 선택하고 배열을 분할하는 함수
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 피벗은 항상 배열의 마지막 요소로 선택
    int i = low - 1; // 작은 요소들의 마지막 인덱스

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 퀵 정렬을 수행하는 함수
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 배열을 분할하고 피벗의 위치를 가져옴

        // 피벗을 기준으로 분할된 두 하위 배열에 대해 재귀적으로 정렬 수행
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 배열을 출력하는 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "정렬 전 배열: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "정렬 후 배열: ";
    printArray(arr, n);

    return 0;
}

 

 

출력 결과

 

정렬 전 배열: 10 7 8 9 1 5
정렬 후 배열: 1 5 7 8 9 10​

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀