DAA - त्वरित सॉर्ट
यह फूट डालो और जीतो के सिद्धांत पर प्रयोग किया जाता है। त्वरित सॉर्ट कई स्थितियों में पसंद का एक एल्गोरिथ्म है क्योंकि इसे लागू करना मुश्किल नहीं है। यह एक अच्छा सामान्य उद्देश्य है और यह निष्पादन के दौरान अपेक्षाकृत कम संसाधनों का उपभोग करता है।
लाभ
चूंकि यह केवल एक छोटे सहायक स्टैक का उपयोग करता है, इसलिए यह इन-प्लेस है।
यह केवल आवश्यकता है n (log n) सॉर्ट करने का समय n आइटम नहीं है।
इसमें एक बेहद छोटा लूप है।
इस एल्गोरिथ्म को पूरी तरह से गणितीय विश्लेषण के अधीन किया गया है, प्रदर्शन के मुद्दों के बारे में बहुत सटीक बयान दिया जा सकता है।
नुकसान
यह पुनरावर्ती है। विशेष रूप से, यदि पुनरावृत्ति उपलब्ध नहीं है, तो कार्यान्वयन अत्यंत जटिल है।
इसे सबसे खराब स्थिति में द्विघात (यानी, एन 2) समय की आवश्यकता होती है।
यह नाजुक है, यानी कार्यान्वयन में एक साधारण गलती किसी का ध्यान नहीं जा सकती है और इसका कारण खराब प्रदर्शन हो सकता है।
त्वरित सॉर्ट किसी दिए गए सरणी को विभाजित करके काम करता है A[p ... r] दो गैर-खाली उप सरणी में A[p ... q] तथा A[q+1 ... r] ऐसे कि हर कुंजी में A[p ... q] में हर कुंजी के बराबर या उससे कम है A[q+1 ... r]।
फिर, दो उप-सरणियों को पुनरावर्ती कॉल के द्वारा त्वरित सॉर्ट में सॉर्ट किया जाता है। विभाजन की सही स्थिति दी गई सरणी और सूचकांक पर निर्भर करती हैq विभाजन प्रक्रिया के एक भाग के रूप में गणना की जाती है।
Algorithm: Quick-Sort (A, p, r)
if p < r then
q Partition (A, p, r)
Quick-Sort (A, p, q)
Quick-Sort (A, q + r, r)ध्यान दें कि संपूर्ण सरणी को क्रमबद्ध करने के लिए, प्रारंभिक कॉल होनी चाहिए Quick-Sort (A, 1, length[A])
पहले चरण के रूप में, क्विक सॉर्ट धुरी के रूप में छांटने के लिए सरणी में किसी एक आइटम को चुनता है। फिर, सरणी को पिवट के दोनों ओर विभाजित किया जाता है। वे तत्व जो धुरी से कम या बराबर हैं, बाईं ओर जाएंगे, जबकि वे तत्व जो धुरी से अधिक या बराबर हैं, दाईं ओर जाएंगे।
ऐरे में विभाजन
विभाजन प्रक्रिया उप-सरणियों को पुनः व्यवस्थित करती है।
Function: Partition (A, p, r)
x ← A[p]
i ← p-1
j ← r+1
while TRUE do
Repeat j ← j - 1
until A[j] ≤ x
Repeat i← i+1
until A[i] ≥ x
if i < j then
exchange A[i] ↔ A[j]
else
return jविश्लेषण
क्विक-सॉर्ट एल्गोरिथ्म की सबसे खराब स्थिति जटिलता है O(n2)। हालांकि, इस तकनीक का उपयोग करके, औसत मामलों में आमतौर पर हम आउटपुट प्राप्त करते हैंO(n log n) समय।