Quicksort
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
이 멘탈 모델부터 시작하세요
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
불필요한 전문용어 없이 동작 방식 이해하기
Average time is O(n log n), but poor pivot choices can lead to O(n²).
In-place variants need little extra array memory, though recursion still uses stack space.
알고리즘을 연속된 의사결정으로 읽기
Understand what one pass/partition/merge guarantees.
Track which region is already finalized.
Reason about comparisons, swaps/moves and extra memory.
Read a tiny input by hand and write down the state after every important operation. For Quicksort, the goal is to make the invariant visible rather than to memorize code.
function quickSort(a) {
if (a.length <= 1) return a;
const pivot = a[Math.floor(a.length / 2)];
const left = a.filter(x => x < pivot);
const equal = a.filter(x => x === pivot);
const right = a.filter(x => x > pivot);
return [...quickSort(left), ...equal, ...quickSort(right)];
}문법을 외우지 마세요. 각 줄에서 바뀌는 상태를 따라가고 위에서 설명한 불변식과 연결하세요.
avg O(n log n), worst O(n²)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
적합한 경우
- Choose based on input size, order, key range, stability and memory limits.
보통 어디에서 문제가 생기는가
- Comparing only average Big-O.
- Forgetting stability, in-place behavior, recursion depth or key-domain assumptions.
전문적인 답변 구조
Discuss pivot strategy and partition scheme. Saying only 'O(n log n)' misses the important worst-case trade-off.
What problem does Quicksort solve?
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
복잡도에 대해 무엇을 언급해야 하나요?
Its typical cost here is avg O(n log n), worst O(n²), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
가장 흔한 실수는 무엇인가요?
Comparing only average Big-O.