PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) (क्विक सॉर्ट: पिवट चयन, पार्टीशनिंग और सबसे खराब स्थिति O(n^2)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Quick Sort partitions an array around a chosen pivot so smaller elements move left and larger elements move right, achieving O(n log n) average speed in-place while degrading to O(n^2) on consistently unbalanced splits.
अध्याय सार: क्विक सॉर्ट एक चुने गए पिवट (Pivot) के आधार पर एरे का विभाजन (Partitioning) कर छोटे तत्व बाएँ और बड़े तत्व दाएँ रखता है; यह इन-प्लेस में औसत O(n log n) गति देता है पर असंतुलित विभाजन से वर्स्ट केस O(n^2) हो सकता है।
Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2): Detailed Notes & Architecture (क्विक सॉर्ट: पिवट चयन, पार्टीशनिंग और सबसे खराब स्थिति O(n^2))
1. Partitioning Mechanics: Lomuto vs Hoare Schemes (पार्टीशनिंग प्रणाली: लोमुटो बनाम होरे विधि)
[EN] Unlike Merge Sort where the heavy work lies in combining, Quick Sort performs its core work BEFORE recursion inside partition(). It picks a pivot and rearranges arr[low..high] in O(n) time so elements <= pivot precede elements >= pivot. Lomuto's scheme picks arr[high] as pivot with a single forward scanner and places the pivot cleanly at its exact final index, whereas Hoare's original scheme uses two inward-moving pointers from both ends—performing roughly 3x fewer swaps and handling duplicate keys far better.
[HI] मर्ज सॉर्ट के विपरीत, क्विक सॉर्ट का मुख्य कार्य रिकर्शन से पहले partition() चरण में होता है। यह O(n) समय में पिवट से छोटे तत्व बाईं ओर और बड़े तत्व दाईं ओर रखता है। लोमुटो (Lomuto) विधि में अंतिम तत्व पिवट बनता है और एक पॉइंटर से काम होता है, जबकि होरे (Hoare) की मूल विधि दोनों सिरों से दो पॉइंटर चलाकर लगभग तीन गुना कम स्वैप करती है और डुप्लीकेट तत्वों पर अधिक कुशल रहती है।
2. Best, Skewed-Ratio & Worst-Case Recurrence Analysis (बेस्ट, आनुपातिक व वर्स्ट-केस कॉम्प्लेक्सिटी विश्लेषण)
[EN] When the pivot splits the array evenly into n/2 and n/2, T(n) = 2T(n/2) + Theta(n) resolves to Theta(n log n). Remarkably, even a fixed lopsided split like 9:1 (T(n) = T(9n/10) + T(n/10) + n) stays Theta(n log n) because tree height remains logarithmic (log_{10/9} n). However, if the pivot consistently hits the minimum or maximum (e.g., picking first/last pivot on an already sorted or reverse-sorted array), T(n) = T(n-1) + Theta(n) degrades to Theta(n^2).
[HI] जब पिवट एरे को लगभग बराबर दो भागों (n/2) में बांटता है, तो T(n) = 2T(n/2) + Theta(n) से Theta(n log n) समय लगता है। यहाँ तक कि 9:1 जैसे निश्चित असमान विभाजन पर भी कुल समय Theta(n log n) ही रहता है। लेकिन यदि हर बार सबसे छोटा या सबसे बड़ा तत्व पिवट चुना जाए (जैसे पहले से सॉर्टेड एरे में अंतिम तत्व पिवट लेना), तो T(n) = T(n-1) + Theta(n) से वर्स्ट केस Theta(n^2) हो जाता है।
3. Pivot Selection Strategies & Introsort Safeguard (पिवट चयन रणनीतियाँ व इंट्रोसॉर्ट सुरक्षा)
[EN] To prevent deterministic O(n^2) traps on sorted inputs or adversarial inputs, Randomized Quick Sort selects a random index in [low, high] and swaps it into pivot position—guaranteeing O(n log n) expected runtime on EVERY input. Median-of-Three chooses the median of arr[low], arr[mid], and arr[high], improving split balance while lowering variance. Industrial libraries like C++ std::sort use Introsort: Quick Sort that switches to Heap Sort if recursion depth exceeds 2*log2(n), guaranteeing O(n log n) worst case.
[HI] सॉर्टेड इनपुट पर O(n^2) से बचने के लिए रैंडमाइज्ड क्विक सॉर्ट [low, high] से यादृच्छिक पिवट चुनता है जिससे हर इनपुट पर औसत O(n log n) गारंटी मिलती है। मीडियन-ऑफ-थ्री (प्रथम, मध्य व अंतिम में से मध्यिका चुनना) और भी बेहतर संतुलन देता है। C++ का std::sort 'Introsort' उपयोग करता है जो रिकर्शन गहराई 2*log2(n) से बढ़ने पर स्वतः Heap Sort में बदलकर O(n log n) वर्स्ट-केस सुरक्षा देता है।
4. In-Place Stack Optimization & Stability Property (इन-प्लेस स्टैक अनुकूलन व स्थिरता गुण)
[EN] Standard Quick Sort is In-Place regarding auxiliary array buffers (O(1) heap memory), though recursion stack consumes O(log n) space on average and O(n) space in the worst case. Using Tail-Call Elimination—always recursing on the SMALLER partition and iterating on the larger partition—strictly bounds worst-case stack space to O(log n)! Standard Quick Sort is NOT stable because partition swaps move equal elements across long spans.
[HI] क्विक सॉर्ट कोई अतिरिक्त डेटा एरे नहीं बनाता, किंतु इसका रिकर्शन स्टैक औसत में O(log n) और वर्स्ट केस में O(n) स्थान ले सकता है। यदि 'टेल-कॉल ऑप्टिमाइजेशन' अपनाकर हमेशा छोटे उप-भाग पर रिकर्शन और बड़े भाग पर लूप चलाया जाए, तो वर्स्ट केस में भी स्टैक स्पेस O(log n) तक सीमित हो जाता है। लंबी छलांग वाले स्वैप के कारण मानक क्विक सॉर्ट नॉन-स्टेबल होता है।
Syntax, Formula & Technical Example (Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2))
int lomutoPartition(int a[], int low, int high) {
int pivot = a[high], i = low - 1;
for (int j = low; j < high; 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[high]; a[high] = t;
return i + 1; // Final sorted index of pivot
}
Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) Quick Reference & Comparison Table
| Quick Sort Scenario | Recurrence & Time | Stack Space & Pivot Rule |
|---|---|---|
| Balanced Split (Best/Avg) | T(n) = 2T(n/2) + n => O(n log n) | Pivot lands near median; O(log n) call stack |
| Skewed 0:(n-1) Split (Worst) | T(n) = T(n-1) + n => O(n^2) | Sorted input with first/last pivot; O(n) stack |
| Randomized / Median-of-3 | Expected O(n log n) for all inputs | Eliminates predictable sorted-array O(n^2) trigger |
| Tail-Recurse Smaller Half | Caps auxiliary stack depth to O(log n) | Recurses smaller segment, loops on larger segment |
Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) Top 20 Bilingual MCQs with Answers
Q1. When does naive Quick Sort (always picking the last element as pivot) hit its O(n^2) worst-case time complexity?
(हमेशा अंतिम तत्व को पिवट चुनने वाला साधारण क्विक सॉर्ट किस इनपुट पर O(n^2) वर्स्ट केस में चला जाता है?)
(A) When the median element happens to sit at the last index
(B) Only when the array contains random distinct integers
(C) Only when n is an odd prime number
(D) When the input array is already sorted (ascending or descending) or all elements are equal (Lomuto)
Correct Answer: (D)
[EN] Picking the extremum every time produces empty + (n-1) partitions, leading to n + (n-1) + ... + 1 = O(n^2).
[HI] पहले से सॉर्टेड (आरोही या अवरोही) एरे में अंतिम तत्व हमेशा न्यूनतम या अधिकतम होता है, जिससे 0 व n-1 का सबसे खराब विभाजन बनता है।
Q2. Suppose Quick Sort always splits the array in a fixed 9:1 ratio (90% left, 10% right) at every recursion level. What is its asymptotic time complexity?
(यदि क्विक सॉर्ट हर स्तर पर एरे को एक निश्चित 9:1 अनुपात (90% और 10%) में विभाजित करे, तो इसकी असिम्प्टोटिक टाइम कॉम्प्लेक्सिटी क्या होगी?)
(A) O(n)
(B) O(n^2)
(C) O(n^(1.9))
(D) O(n log n)
Correct Answer: (D)
[EN] Recurrence T(n) = T(9n/10) + T(n/10) + cn has tree depth log_{10/9}(n) with <= cn work per level, giving Theta(n log n)!
[HI] रिकरेंस T(n) = T(9n/10) + T(n/10) + cn में ट्री की अधिकतम गहराई लॉगरिदमिक (log_{10/9} n) रहती है, अतः कुल समय O(n log n) ही होता है।
Q3. How does Randomized Quick Sort protect against worst-case O(n^2) inputs?
(रैंडमाइज्ड क्विक सॉर्ट वर्स्ट-केस O(n^2) इनपुट से बचाव कैसे करता है?)
(A) By eliminating partitioning entirely
(B) By sorting the array with Merge Sort before picking pivots
(C) By turning Quick Sort into a stable algorithm
(D) By choosing a random element in [low, high] as pivot so no fixed input ordering can force bad splits reliably
Correct Answer: (D)
[EN] Random pivot choice makes expected time O(n log n) regardless of whether input is sorted, reversed, or adversarial.
[HI] यादृच्छिक पिवट चुनने से कोई भी पूर्व-निर्धारित क्रम लगातार खराब विभाजन नहीं करा पाता और अपेक्षित समय O(n log n) रहता है।
Q4. What is the worst-case recursion call stack space of standard unoptimized Quick Sort, and how can it be reduced to O(log n)?
(मानक क्विक सॉर्ट का वर्स्ट-केस कॉल स्टैक स्पेस कितना होता है और इसे O(log n) तक कैसे घटाया जा सकता है?)
(A) Worst case is O(1); reduced by using Lomuto partition
(B) Worst case is O(n^2); reduced by picking arr[0] as pivot
(C) Worst case is always O(log n) without any changes
(D) Worst case is O(n); reduced to O(log n) by recursing ONLY on the smaller partition and looping on the larger half
Correct Answer: (D)
[EN] Recursing on the smaller subarray guarantees problem size drops at least by half per stack frame (tail-call elimination).
[HI] पहले छोटे उप-भाग पर रिकर्शन और बड़े भाग पर इटरेटिव लूप चलाने से हर स्टैक स्तर पर आकार कम से कम आधा हो जाता है (अधिकतम गहराई O(log n))।
Q5. Compare Lomuto and Hoare partitioning schemes: which statement is accurate?
(लोमुटो (Lomuto) और होरे (Hoare) पार्टीशनिंग विधियों की सही तुलना कौन सी है?)
(A) Lomuto partition performs fewer swaps than Hoare
(B) Hoare partition performs about 3x fewer swaps on average and handles duplicate keys better than Lomuto
(C) Lomuto partition is guaranteed stable
(D) Hoare partition always places the pivot at the returned index j
Correct Answer: (B)
[EN] Hoare's two-pointer scheme swaps only inversions from opposite ends and avoids O(n^2) slowdowns on all-equal arrays better than naive Lomuto.
[HI] होरे पार्टीशन दोनों सिरों से दो पॉइंटर चलाता है जिससे लोमुटो की तुलना में औसतन तीन गुना कम स्वैप होते हैं और समान तत्वों पर बेहतर प्रदर्शन मिलता है।
Q6. Trace Lomuto partition on arr = [10, 80, 30, 90, 40, 50, 70] using pivot = 70 (last element). Where does 70 land finally?
(एरे [10, 80, 30, 90, 40, 50, 70] पर pivot = 70 के साथ लोमुटो पार्टीशन चलाने पर 70 किस इंडेक्स पर और किस अवस्था में पहुंचेगा?)
(A) Index 4, giving [10, 30, 40, 50, 70, 90, 80]
(B) Index 5, giving [10, 30, 40, 50, 80, 70, 90]
(C) Index 0, giving [70, 80, 30, 90, 40, 50, 10]
(D) Index 3, giving [10, 30, 40, 70, 80, 90, 50]
Correct Answer: (A)
[EN] Elements <= 70 are 10, 30, 40, 50 (4 elements), so after placing them at indices 0..3, pivot 70 swaps with 80 at index 4.
[HI] 70 से छोटे 4 तत्व (10, 30, 40, 50) बाईं ओर इंडेक्स 0..3 में जाते हैं और पिवट 70 इंडेक्स 4 पर बैठता है: [10, 30, 40, 50, 70, 90, 80]।
Q7. Why is standard Quick Sort NOT a stable sorting algorithm?
(मानक क्विक सॉर्ट को एक स्टेबल (Stable) सॉर्टिंग एल्गोरिदम क्यों नहीं माना जाता?)
(A) Because it uses O(n) auxiliary space
(B) Because its best case is O(n^2)
(C) Swapping elements across distant indices during partitioning can reverse the relative order of duplicate keys
(D) Because it cannot sort floating-point numbers
Correct Answer: (C)
[EN] Both Lomuto and Hoare schemes swap elements far apart around the pivot without preserving prior duplicate order.
[HI] पार्टीशनिंग के दौरान दूर स्थित तत्वों के स्वैप होने से समान मान वाले तत्वों का मूल क्रम बदल सकता है।
Q8. What does 'Median-of-Three' pivot selection inspect?
('मीडियन-ऑफ-थ्री (Median-of-Three)' पिवट चयन तकनीक किन तत्वों की जांच करती है?)
(A) The exact arithmetic mean of all n elements
(B) The median value among the first (low), middle (mid), and last (high) elements of the subarray
(C) Three randomly chosen subarrays of size n/3
(D) The first three elements arr[0], arr[1], arr[2]
Correct Answer: (B)
[EN] Taking the median of arr[low], arr[mid], arr[high] defeats sorted/reverse-sorted worst-case traps in O(1) time.
[HI] यह सब-एरे के पहले, मध्य व अंतिम तीन तत्वों में से मध्यिका मान (Median) को पिवट चुनकर सॉर्टेड-एरे वर्स्ट केस से बचाती है।
Q9. How does C++ STL's 'Introsort' (std::sort) ensure an O(n log n) worst-case guarantee alongside Quick Sort speed?
(C++ STL का 'Introsort (std::sort)' क्विक सॉर्ट की गति के साथ O(n log n) वर्स्ट-केस की गारंटी कैसे देता है?)
(A) It copies elements into a Hash Table
(B) It runs Merge Sort twice in parallel
(C) It switches from Quick Sort to Heap Sort whenever recursion depth exceeds 2 * floor(log2 n)
(D) It switches to Bubble Sort when depth exceeds n/2
Correct Answer: (C)
[EN] Introsort monitors recursion depth; if deep skewed splits arise, Heap Sort guarantees O(n log n) worst time in O(1) extra space.
[HI] जब रिकर्शन गहराई 2*log2(n) से अधिक होने लगती है तो Introsort तुरंत Heap Sort पर स्विच होकर O(n log n) की पक्की सुरक्षा देता है।
Q10. What is the recurrence relation for Quick Sort's WORST case?
(क्विक सॉर्ट के वर्स्ट केस का रिकरेंस समीकरण क्या होता है?)
(A) T(n) = T(n/2) + Theta(1)
(B) T(n) = 2T(n-1) + Theta(1)
(C) T(n) = 2T(n/2) + Theta(n)
(D) T(n) = T(n - 1) + Theta(n)
Correct Answer: (D)
[EN] When one partition gets 0 elements and the other gets n - 1 elements after O(n) partition work, T(n) = T(n-1) + Theta(n) = Theta(n^2).
[HI] एक तरफ 0 और दूसरी तरफ n-1 तत्व बचने पर समीकरण T(n) = T(n-1) + Theta(n) बनता है जिसका हल Theta(n^2) है।
Q11. Why is Quick Sort generally faster than Merge Sort on large in-memory primitive arrays despite having the same O(n log n) average complexity?
(समान O(n log n) औसत कॉम्प्लेक्सिटी के बावजूद RAM में एरे सॉर्टिंग में क्विक सॉर्ट प्रायः मर्ज सॉर्ट से तेज क्यों चलता है?)
(A) Quick Sort never uses recursion
(B) Quick Sort sorts in-place with tight sequential CPU cache locality and avoids allocating/copying O(n) temp buffers
(C) Quick Sort makes fewer comparisons in the worst case
(D) Quick Sort runs in O(n) time on all inputs
Correct Answer: (B)
[EN] No dynamic O(n) buffer allocation and sequential array scans maximize L1/L2 cache hit rates.
[HI] O(n) अतिरिक्त बफर आवंटन/कॉपी की जरूरत न होने और बेहतर CPU कैश लोकैलिटी के कारण क्विक सॉर्ट व्यावहारिक रूप से तेज रहता है।
Q12. How can Quick Sort find the k-th smallest element in an unsorted array in O(n) AVERAGE time (Quickselect)?
(क्विक सॉर्ट की पार्टीशन तकनीक से किसी अनसॉर्टेड एरे में k-वां सबसे छोटा तत्व औसत O(n) समय में कैसे खोजा जाता है (Quickselect)?)
(A) Build a Max-Heap of size n and pop k times
(B) Pick k random pivots simultaneously
(C) After partitioning at p, recurse ONLY into the single side (left or right) containing index k - 1
(D) Partition until the entire array is sorted then return arr[k-1]
Correct Answer: (C)
[EN] Quickselect discards the irrelevant side: T(n) = T(n/2) + O(n) solves to O(n) average (worst case O(n^2)).
[HI] पार्टीशन के बाद केवल उसी एक हिस्से (बाएँ या दाएँ) में आगे बढ़ने से T(n) = T(n/2) + n बनता है, जो औसत O(n) समय देता है।
Q13. In Quick Sort, after partition() finishes and returns pivot index p (Lomuto), which invariant holds for arr[p]?
(लोमुटो partition() पूरा होकर इंडेक्स p लौटाने के बाद arr[p] के बारे में कौन सी बात सदैव सत्य होती है?)
(A) arr[p] must still be moved during the next merge step
(B) arr[p] is always the global minimum of the array
(C) All elements to the right of p are strictly smaller than arr[p]
(D) arr[p] is already placed in its final sorted position and need not be included in either recursive call
Correct Answer: (D)
[EN] Everything in arr[low..p-1] is <= arr[p] and everything in arr[p+1..high] is > arr[p], fixing arr[p] permanently.
[HI] arr[p] अपने अंतिम सॉर्टेड स्थान पर बैठ चुका होता है, इसलिए दोनों रिकर्सिव कॉल्स (low..p-1 व p+1..high) इसे छोड़कर चलती हैं।
Q14. If an array already contains ALL identical elements like [7, 7, 7, 7, 7], what happens under basic Lomuto Quick Sort?
(यदि एरे के सभी तत्व समान हों जैसे [7, 7, 7, 7, 7], तो साधारण लोमुटो क्विक सॉर्ट में क्या होगा?)
(A) It crashes with division by zero
(B) It achieves O(1) time
(C) It finishes in O(n) best case automatically
(D) Every partition puts all n-1 elements on the left (0 on right), degrading to O(n^2)
Correct Answer: (D)
[EN] Because a[j] <= pivot is true for every element, basic Lomuto fails to split symmetrically unless 3-way (Dutch National Flag) partitioning is used.
[HI] a[j] <= pivot हर बार सत्य होने से लोमुटो 0 और n-1 में बंटकर O(n^2) हो जाता है (इसे 3-वे पार्टीशनिंग हल करती है)।
Q15. Which partition variant splits keys into three regions (< pivot, == pivot, > pivot) to achieve O(n) time when many duplicates exist?
(अनेक डुप्लीकेट तत्व होने पर O(n) समय देने के लिए कौन सी विधि डेटा को तीन भागों (<, ==, > पिवट) में बांटती है?)
(A) Lomuto Single-Scan Partition
(B) Binary Merge Partition
(C) 3-Way Quick Sort (Dutch National Flag Partition)
(D) Radix Bucket Partition
Correct Answer: (C)
[EN] Grouping all equal keys together in the middle skips recurring on duplicates completely.
[HI] समान तत्वों को बीच के खंड में एकत्रित कर छोड़ देने से डुप्लीकेट-बहुल डेटा O(n) में सॉर्ट हो जाता है।
Q16. Which statement is NOT true about standard Quick Sort?
(मानक क्विक सॉर्ट के बारे में इनमें से कौन सा कथन सत्य नहीं है?)
(A) It sorts in-place without needing an O(n) merge buffer
(B) It guarantees O(n log n) worst-case time complexity on every possible input without randomization or fallback
(C) It is an unstable sorting algorithm
(D) Its average-case time complexity is O(n log n)
Correct Answer: (B)
[EN] Deterministic Quick Sort has an O(n^2) worst case, unlike Merge Sort and Heap Sort.
[HI] बिना किसी फॉल-बैक (जैसे Introsort) के मानक क्विक सॉर्ट का वर्स्ट केस O(n log n) नहीं बल्कि O(n^2) होता है।
Q17. Within Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2), which quick sort scenario directly maps to: "T(n) = 2T(n/2) + n => O(n log n)"?
(Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) में कौन सा Quick Sort Scenario सीधे "T(n) = 2T(n/2) + n => O(n log n)" से संबंधित है?)
(A) Randomized / Median-of-3
(B) Skewed 0:(n-1) Split (Worst)
(C) Balanced Split (Best/Avg)
(D) Tail-Recurse Smaller Half
Correct Answer: (C)
[EN] In Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2), 'Balanced Split (Best/Avg)' handles 'T(n) = 2T(n/2) + n => O(n log n)' (Pivot lands near median; O(log n) call stack).
[HI] Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) में 'Balanced Split (Best/Avg)' का कार्य/विवरण 'T(n) = 2T(n/2) + n => O(n log n)' (Pivot lands near median; O(log n) call stack) है।
Q18. Which option accurately describes 'Skewed 0:(n-1) Split (Worst)' in Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2)?
(Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) के संदर्भ में 'Skewed 0:(n-1) Split (Worst)' की सही विशेषता कौन सी है?)
(A) Expected O(n log n) for all inputs
(B) T(n) = 2T(n/2) + n => O(n log n)
(C) Caps auxiliary stack depth to O(log n)
(D) T(n) = T(n-1) + n => O(n^2)
Correct Answer: (D)
[EN] 'Skewed 0:(n-1) Split (Worst)' provides 'T(n) = T(n-1) + n => O(n^2)' — key point: Sorted input with first/last pivot; O(n) stack.
[HI] 'Skewed 0:(n-1) Split (Worst)' का मुख्य विवरण 'T(n) = T(n-1) + n => O(n^2)' है (Sorted input with first/last pivot; O(n) stack)।
Q19. In Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2), identify the correct parameter for the specification: "Expected O(n log n) for all inputs".
(Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) में "Expected O(n log n) for all inputs" विवरण किस विकल्प के लिए सही है?)
(A) Skewed 0:(n-1) Split (Worst)
(B) Tail-Recurse Smaller Half
(C) Balanced Split (Best/Avg)
(D) Randomized / Median-of-3
Correct Answer: (D)
[EN] 'Randomized / Median-of-3' corresponds to 'Expected O(n log n) for all inputs' (Eliminates predictable sorted-array O(n^2) trigger).
[HI] 'Randomized / Median-of-3' का संबंध 'Expected O(n log n) for all inputs' (Eliminates predictable sorted-array O(n^2) trigger) से है।
Q20. Considering Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2), what key behavior defines 'Tail-Recurse Smaller Half'?
(Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) में 'Tail-Recurse Smaller Half' की मुख्य भूमिका या मान क्या है?)
(A) Expected O(n log n) for all inputs
(B) T(n) = 2T(n/2) + n => O(n log n)
(C) Caps auxiliary stack depth to O(log n)
(D) T(n) = T(n-1) + n => O(n^2)
Correct Answer: (C)
[EN] 'Tail-Recurse Smaller Half' represents 'Caps auxiliary stack depth to O(log n)' (Recurses smaller segment, loops on larger segment).
[HI] 'Tail-Recurse Smaller Half' का अर्थ/मान 'Caps auxiliary stack depth to O(log n)' है (Recurses smaller segment, loops on larger segment)।
Quick Sort: Partitioning, Pivot Selection, Best O(n log n), Worst O(n^2) — Exam FAQs
Q1: Why is Quick Sort called 'Quick' if its worst case is O(n^2)?
वर्स्ट केस O(n^2) होने पर भी इसे 'क्विक (तेज)' सॉर्ट क्यों कहा जाता है?
[EN] With randomized or median-of-3 pivot selection, the O(n^2) case has negligible probability; its inner loop has minimal overhead, sequential cache efficiency, and zero O(n) allocation, making it fastest in real-world RAM sorting.
[HI] रैंडमाइज्ड या मीडियन-ऑफ-थ्री पिवट से O(n^2) की संभावना लगभग शून्य हो जाती है, और बिना अतिरिक्त एरे बनाए कैश-अनुकूल लूप चलने से यह RAM में वास्तविक रूप से सबसे तेज चलता है।
Q2: Is Quick Sort better than Merge Sort for linked lists?
क्या लिंक्ड लिस्ट के लिए क्विक सॉर्ट मर्ज सॉर्ट से बेहतर है?
[EN] No. Linked lists lack O(1) random indexing for median-of-3 or Hoare backward pointers, and Merge Sort already sorts linked lists stably in O(n log n) worst time with O(1) extra space.
[HI] नहीं। लिंक्ड लिस्ट में पीछे से पॉइंटर चलाने या रैंडम पिवट लेने की सुविधा नहीं होती, जबकि मर्ज सॉर्ट लिंक्ड लिस्ट पर O(n log n) वर्स्ट केस व O(1) डेटा स्पेस में स्थिरता से काम करता है।
Q3: Does Quick Sort work well when all elements are equal?
जब एरे के सभी तत्व एक समान हों, तो क्या मानक क्विक सॉर्ट अच्छा काम करता है?
[EN] Naive Lomuto partition degrades to O(n^2) on equal keys. Using Hoare partition or 3-Way (Dutch National Flag) partitioning solves duplicate-heavy arrays in O(n) to O(n log n) time.
[HI] साधारण लोमुटो विधि समान तत्वों पर O(n^2) में धीमी पड़ जाती है; इसके लिए होरे पार्टीशन या 3-वे (डच नेशनल फ्लैग) पार्टीशनिंग का उपयोग किया जाता है।
Post a Comment
Post a Comment