📚 퀵소트 (QuickSort) : 원리, 방식 비교, 자바 구현까지

✨ 퀵소트란?

퀵소트(QuickSort)는 분할정복(Divide and Conquer) 전략을 활용한 정렬 알고리즘입니다.

피벗(Pivot)을 기준으로 배열을 분할하고, 각 부분 배열에 대해 재귀적으로 정렬을 수행하여 전체 정렬을 완성합니다.

---

⚙️ 작동 원리: 분할정복

퀵소트는 다음 세 단계로 구성됩니다.

---

📌 분할(Partition)의 의미

• 배열의 값을 피벗보다 작거나 같은 값은 왼쪽, 큰 값은 오른쪽으로 분리

• 자기 자신과도 비교하고 필요하면 스왑

• 이 과정에서 피벗의 위치는 정렬된 상태로 확정됨

• 이후 좌/우 하위 배열을 계속 퀵소트로 정렬

---

🧠 피벗과 파티셔닝은 어떻게 이루어지는가?

파티셔닝이란 피벗 기준으로 배열 요소를 비교하며 자리를 바꾸는 과정입니다.

• 일반적으로 모든 인덱스를 피벗과 비교합니다.

• 자기 자신도 비교 대상이며, 조건 충족 시 자기 자신과도 스왑이 발생합니다.

• 비교 방식 및 스왑 방식은 분할 알고리즘에 따라 달라집니다.

---

🧭 분할 방식 종류: Hoare vs. Lomuto

---

🧪 실행 예시 비교 (공통 배열:

[34, 7, 23, 32, 5, 62]

)

✅ Hoare 방식 (피벗: 23)

1. swap(0,4) → [5, 7, 23, 32, 34, 62]

2. left=3, right=2 → 종료

→ 결과: [5, 7, 23, 32, 34, 62]

✅ Lomuto 방식 (피벗: 62)

• 자기 자신과 6번 스왑 발생

• 값 재배치 없이 그대로 [34, 7, 23, 32, 5, 62]

→ 분할만 완료된 상태 (정렬은 이후 진행됨)

---

💻 자바 구현 예제

1. Hoare 분할 방식

int pivot = arr[(left + right) / 2];
while (left <= right) {
    while (arr[left] < pivot) left++;
    while (arr[right] > pivot) right--;
    if (left <= right) {
        swap(arr, left, right);
        left++; right--;
    }
}

2. Lomuto 분할 방식

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

---

✅ 정리 요약