Quicksort: partition, duplicates और stack
Contract और पूर्वज्ञान
मौजूदा sorting और asymptotic-bounds पाठ आधार हैं। यहाँ inclusive A[lo..hi] पर Lomuto partition है: pivot A[hi], comparison <=। दूसरी schemes में returned index और trace अलग हो सकते हैं; उन्हें मिलाएँ नहीं।
1. Partition निकालें
p=A[hi], i=lo−1 रखें। j=lo से hi−1 तक: यदि A[j]<=p, i बढ़ाएँ और A[i],A[j] swap करें। अंत में A[i+1],A[hi] swap करके q=i+1 लौटाएँ। हर iteration से पहले A[lo..i]<=p, A[i+1..j−1]>p, A[j..hi−1] unclassified और A[hi]=p है। Empty ranges मान्य हैं। सफल comparison छोटी region बढ़ाता है; असफल comparison बड़ी region बढ़ाता है। अंतिम swap pivot को इनके बीच रखता है।
Quicksort: lo>=hi हो तो return; q=partition(lo,hi); sort(lo,q−1); sort(q+1,hi)। दोनों recursive ranges से pivot बाहर है। q endpoint होने पर भी size घटता है और algorithm समाप्त होता है। Partition से दोनों sides अपने-आप sorted नहीं होतीं।
हल किया trace [4,2,4,1,3]: p=3। j=0 fail; j=1 success से [2,4,4,1,3]; j=2 fail; j=3 success से [2,1,4,4,3]। अंतिम swap: [2,1,3,4,4], q=2। Left [2,1] को अभी sort करना है। Pivot comparisons चार हुए।
2. Balanced और unbalanced work
n-element partition Θ(n) है। Balanced split पर 2T(n/2)+Θ(n)=Θ(n log n)। Endpoint pivot पर T(n−1)+Θ(n)=Θ(n²), क्योंकि comparison sum (n−1)+...+1=n(n−1)/2 है। Last-element pivot के साथ ascending distinct input worst case है। Distinct keys पर random pivot का expected time Θ(n log n), लेकिन quadratic worst case फिर भी संभव है।
इस <= convention में all-equal array पर हर बार q=hi आता है। Random pivot record लेने से भी सभी keys बराबर रहती हैं, इसलिए time quadratic रहता है। Three-way partition <p, =p, >p groups बनाता और केवल strict groups recursively sort करता है। All-equal array एक linear scan में समाप्त हो सकता है। यह अलग algorithm है; Lomuto trace में इसे चुपचाप न लगाएँ।
3. Space, stability और safeguards
Partition का auxiliary storage O(1), लेकिन recursive quicksort का stack balanced case में Θ(log n) और worst case में Θ(n) है। In-place कहते समय बताएँ कि stack गिना है या नहीं। O(log n) stack guarantee के लिए छोटी side recursively sort करें, बड़ी side को loop से process करें। हर nested call active size कम-से-कम आधा करता है। Poor pivot का quadratic time इससे नहीं सुधरता।
सामान्य swapping quicksort unstable है: [2a,2b,1] पहली partition में [1,2b,2a] बनता है। Equal records का क्रम उलट गया। केवल <= से merge जैसी stability नहीं मिलती। वास्तविक C में lo−1 के लिए signed index type लें; lo=0 पर unsigned wrap होगा। A[hi] पढ़ने से पहले base case जाँचें। Pseudocode valid bounds और numeric type में फिट values मानता है।
जाँचें
Trace से पहले partition convention लिखें। Expected और worst-case time अलग रखें; partition space और पूरे recursive stack को भी अलग रखें। Distinct-key random analysis duplicates की समस्या नहीं सुलझाता।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. बताए partition में [4,2,4,1,3] का q:
A. 0 B. 1 C. 2 D. 4
उत्तर: C
A: 3 से छोटे दो records हैं।
B: Index 1 pivot से पहले है।
C: अंतिम array [2,1,3,4,4] है।
D: 3 maximum नहीं।
P02. इस partition के बाद सही recursive ranges?
A. [lo,q] और [q,hi] B. [lo,q−1] और [q+1,hi] C. केवल [lo,q] D. फिर पूरा range
उत्तर: B
A: q शामिल करने से progress रुक सकती है।
B: Final pivot बाहर रखें।
C: दोनों sides process हों।
D: Size नहीं घटेगा।
P03. <= Lomuto में all-equal input का time:
A. Θ(1) B. Θ(n) C. Θ(n log n) D. Θ(n²)
उत्तर: D
A: सभी records देखे जाएँगे।
B: Equal group एक साथ नहीं हटता।
C: Splits balanced नहीं।
D: Pivot hi पर, शेष n−1 records।
P04. खराब pivots के बावजूद O(log n) stack कैसे?
A. हमेशा left recurse B. छोटी side recurse; बड़ी loop C. हमेशा last pivot D. Base case हटाएँ
उत्तर: B
A: Left side बड़ी हो सकती है।
B: Nested size कम-से-कम आधा होता है।
C: Last pivot depth नहीं रोकता।
D: Termination टूटेगा।
P05. Sorted 5 distinct elements, last pivot: कुल pivot comparisons?
A. 4 B. 8 C. 10 D. 25
उत्तर: C
A: यह पहली partition है।
B: योग 4+3+2+1 है।
C: 4+3+2+1=10।
D: n² exact count नहीं।
P06. सामान्य swapping quicksort पर कौन-सा सही है?
A. हमेशा stable B. Random pivot worst case हटाता है C. Partition को Θ(n) buffer चाहिए D. Equal records उलट सकते हैं
उत्तर: D
A: [2a,2b,1] counterexample है।
B: Expectation बदलती है, सभी outcomes नहीं।
C: Partition constant extra storage लेता है।
D: [2a,2b,1] से [1,2b,2a] बनता है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन