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.