#include <stdio.h>

void quick_sort(int arr[], int left, int right) {
    if (left >= right) return;
    // 종료 조건: 정렬할 구간에 원소가 1개 이하일 때

    int pivot = arr[left];  // 기준값(pivot): 맨 앞 원소
    int i = left + 1;       // 왼쪽에서 오른쪽으로 이동할 포인터
    int j = right;          // 오른쪽에서 왼쪽으로 이동할 포인터
    int temp;

    while (i <= j) {
        // pivot보다 큰 값을 만날 때까지 i를 오른쪽으로 이동
        while (i <= right && arr[i] <= pivot) i++;

        // pivot보다 작은 값을 만날 때까지 j를 왼쪽으로 이동
        while (j > left && arr[j] >= pivot) j--;

        if (i > j) {
            // i와 j가 엇갈리면 pivot과 arr[j]를 교환
            temp = arr[left];
            arr[left] = arr[j];
            arr[j] = temp;
        } else {
            // i와 j가 엇갈리지 않으면 두 값을 교환
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 왼쪽 파티션 정렬
    quick_sort(arr, left, j - 1);

    // 오른쪽 파티션 정렬
    quick_sort(arr, j + 1, right);
}

int main() {
    int arr[8] = {5, 3, 8, 4, 2, 7, 1, 6};

    quick_sort(arr, 0, 7);  // 전체 배열 정렬

    for (int i = 0; i < 8; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}