क्विक सॉर्ट

क्विक सॉर्ट (Quicksort) आंकड़ों को एक क्रम में लाने वाला (sorting) कलनविधि(अल्गोरिद्म) है। यह मर्ज सॉर्ट की तरह ही एक बांटो और जीतो (डिवाइड ऐण्ड कॉन्कर) एल्गोरिथ्म है। यह दिए गए आंकड़ों में से एक सदस्य को धुरी के रूप में चुनता है और चुने हुए धुरी के चारों ओर दिए गए सरणी को विभाजित करता है। क्विकसॉर्ट के कई अलग-अलग संस्करण हैं जो विभिन्न तरीकों से धुरी उठाते हैं। हमेशा पहले तत्व को पिवट के रूप में चुनें। हमेशा अंतिम तत्व को धुरी के रूप में चुनें (नीचे लागू किया गया) धुरी के रूप में एक यादृच्छिक तत्व चुनें। मध्यिका को धुरी के रूप में चुनें।

क्विक सॉर्ट में प्रमुख प्रक्रिया विभाजन () है। विभाजन का लक्ष्य, एक सरणी और धुरी के रूप में सरणी का एक तत्व x दिया गया है, x को छांटे गए सरणी में अपनी सही स्थिति पर रखें और x से पहले सभी छोटे तत्वों (x से छोटे) को डालें, और बाद में सभी बड़े तत्वों (x से अधिक) को डालें। एक्स। यह सब रैखिक समय में किया जाना चाहिए।

क्विक सॉर्ट के लिए एल्गोरिथम

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

विभाजन एल्गोरिथम

विभाजन करने के कई तरीके हो सकते हैं, निम्नलिखित छद्म कोड CLRS पुस्तक में दी गई विधि को अपनाते हैं। तर्क सरल है, हम बाएं तत्व से शुरू करते हैं और छोटे (या बराबर) तत्वों के सूचकांक पर नज़र रखते हैं। ट्रैवर्सिंग करते समय, यदि हमें कोई छोटा तत्व मिलता है, तो हम वर्तमान तत्व को गिरफ्तारी [i] के साथ स्वैप करते हैं। अन्यथा हम वर्तमान तत्व की उपेक्षा करते हैं।

/ * कम -> प्रारंभिक सूचकांक, उच्च -> अंत सूचकांक * / क्विक सॉर्ट (गिरफ्तार [], निम्न, उच्च) {

   यदि (कम <उच्च)
   {
       / * pi इंडेक्स विभाजन कर रहा है, अब [pi] गिरफ्तार है
          सही जगह पर * /
       पी = विभाजन (गिरफ्तारी, कम, उच्च);

       क्विक सॉर्ट (गिरफ्तारी, कम, पीआई - 1); // पी से पहले
       क्विक सॉर्ट (गिरफ्तारी, पीआई + 1, उच्च); // पी के बाद
   }

}

विभाजन का चित्रण ():

गिरफ्तार [] = {१०, 10०, 10०, ३०, ९ ०, ४०, ५०, {०} सूचकांक: 0 1 2 3 4 5 6

कम = 0, उच्च = 6, धुरी = गिरफ्तारी [h] = 70 छोटे तत्व का प्रारंभिक सूचकांक, i = -1

जे = निम्न से उच्च -1 तक के तत्वों का पारगमन j = 0: चूंकि गिरफ्तारी [j] <= pivot, i ++ और swap (गिरफ्तारी [i], गिरफ्तारी [j]) मैं = ० arr [] = {10, 80, 30, 90, 40, 50, 70} // मैं और जम्मू के रूप में कोई परिवर्तन नहीं

j = 1: गिरफ्तारी के बाद से [j]> धुरी, कुछ न करें // I और गिरफ्तारी में कोई बदलाव नहीं []

j = 2: गिरफ्तारी के बाद से [j] <= pivot, i ++ और swap (arr [i], arrest [j]) मैं = १ arr [] = {10, 30, 80, 90, 40, 50, 70} // हम 80 और 30 स्वैप करते हैं

j = 3: चूंकि गिरफ्तारी [j]> धुरी, कुछ भी नहीं // I और गिरफ्तारी में कोई बदलाव नहीं []

j = 4: चूंकि गिरफ्तारी [j] <= pivot, i ++ और swap (गिरफ्तारी [i], गिरफ्तारी [j]) मैं = २ arr [] = {10, 30, 40, 90, 80, 50, 70} // 80 और 40 स्वैप किया गया j = 5: चूंकि गिरफ्तारी [j] <= pivot, i ++ और swap arrest [i] गिरफ्तारी [j] के साथ मैं = ३ arr [] = {10, 30, 40, 50, 80, 90, 70} // 90 और 50 स्वैप

हम लूप से बाहर आते हैं क्योंकि j अब हाई -1 के बराबर है। अंत में हम अदला-बदली करके सही स्थिति में पिवट रखते हैं गिरफ्तार [i + 1] और गिरफ्तार [उच्च] (या धुरी) arr [] = {10, 30, 40, 50, 70, 90, 80} // 80 और 70 Swapped

अब 70 अपने सही स्थान पर है। से छोटे सभी तत्व 70 इससे पहले हैं और 70 से अधिक सभी तत्व बाद में हैं यह।

आवश्यक समय

सबसे खराब स्थिति O(n2), सर्वश्रेष्ठ-स्थिति प्रदर्शन O(n लॉग एन) , (सरल विभाजन) या O (n) (तीन-तरफ़ा विभाजन और समान कुंजियाँ), औसत प्रदर्शन ओ (एन लॉग एन)