퀵 정렬
분할 정복을 알아봅니다
퀵 정렬은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
분할 정복
퀵 정렬은 분할 정복 정렬입니다. 피벗을 선택하고 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 오도록 배열을 분할한 다음 각 부분을 재귀적으로 정렬합니다.
평균 시간 복잡도는 O(n log n)입니다.
분할 단계
핵심 개념은 분할입니다. 피벗을 기준으로 배열을 재배치하여 피벗 왼쪽의 모든 원소가 더 작고 오른쪽의 모든 원소가 더 크도록 합니다. 그러면 피벗은 최종 정렬 위치에 놓입니다.
Lomuto 분할 방식
Lomuto 방식은 마지막 원소를 피벗으로 사용합니다. 작은 원소들의 경계를 나타내는 i 인덱스를 유지하면서 배열을 순회하고 교환합니다.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}재귀적 정렬
퀵 정렬은 분할을 수행한 다음 피벗 양쪽의 두 하위 배열에 대해 재귀 호출을 합니다. 하위 배열의 크기가 0 또는 1인 경우가 기저 사례입니다.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}좋은 피벗 선택하기
좋지 않은 피벗(예를 들어 정렬된 입력에서 항상 마지막 원소를 선택하는 경우)은 O(n²) 동작을 일으킵니다. 더 나은 선택은 분할을 보다 고르게 나눕니다.
- 세 값의 중앙값
- 무작위 피벗
세 값의 중앙값
세 값의 중앙값 방식은 첫 번째, 중간, 마지막 원소의 중앙값을 피벗으로 선택하여 이미 정렬된 데이터에서 최악의 동작이 발생하는 것을 피합니다.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}최악의 경우 분석
모든 분할이 원소 하나만 떼어 내면 재귀 깊이가 n이 되고 비용은 O(n²)이 됩니다. 정렬되었거나 역순으로 정렬된 입력에서 고정된 피벗을 사용할 때 이러한 상황이 발생합니다.
무작위화를 적용하면 최악의 경우가 발생할 가능성이 매우 낮아집니다.
무작위 피벗
분할하기 전에 무작위 원소를 피벗 위치로 교환하면 악의적으로 구성된 입력에 대비할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}제자리 정렬과 비안정성
퀵 정렬은 평균적으로 O(log n)의 스택 공간만 사용하여 제자리에서 정렬합니다. 그러나 안정적이지는 않습니다. 분할 과정의 교환으로 같은 원소의 순서가 바뀔 수 있습니다.
꼬리 호출 최적화
더 작은 절반을 먼저 재귀 호출하고 더 큰 절반은 반복문으로 처리하면 스택 깊이가 O(log n)으로 제한되어 큰 배열에서 스택 오버플로를 방지할 수 있습니다.
문자열 정렬
비교 가능한 모든 형식에 동일한 구조를 적용할 수 있습니다. 여기서는 퀵 정렬로 정수 배열을 정렬하지만, 비교 방식을 바꾸면 다른 형식도 처리할 수 있습니다.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}빠른 확인
퀵 정렬에 대한 이해도를 확인해 보세요.
정리
퀵 정렬을 배웠습니다.
- 피벗을 기준으로 분할한 다음 각 부분을 재귀적으로 정렬합니다
- 평균 O(n log n), 최악의 경우 O(n²)입니다
- 세 값의 중앙값 또는 무작위 피벗을 사용하면 최악의 경우를 피할 수 있습니다
- 제자리 정렬이지만 안정적이지는 않습니다
자주 묻는 질문
“퀵 정렬” 강의는 무료인가요?
네 — “퀵 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“퀵 정렬”에서 뭘 배우나요?
분할 정복을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“퀵 정렬” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.